HDU_5528_Count a * b

来源:http://www.cnblogs.com/edward108/archive/2017/10/08/7636856.html
-Advertisement-
Play Games

Count a * b Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 872 Accepted Submission(s): 315 Pro ...


Count a * b

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 872    Accepted Submission(s): 315


Problem Description Marry likes to count the number of ways to choose two non-negative integers a and b less than m to make a×b mod m0.

Let's denote f(m) as the number of ways to choose two non-negative integers a and b less than m to make a×b mod m0.

She has calculated a lot of f(m) for different m, and now she is interested in another function g(n)=m|nf(m). For example, g(6)=f(1)+f(2)+f(3)+f(6)=0+1+4+21=26. She needs you to double check the answer.



Give you n. Your task is to find g(n) modulo 264.
 

 

Input The first line contains an integer T indicating the total number of test cases. Each test case is a line with a positive integer n.

1T20000
1n109
 

 

Output For each test case, print one integer s, representing g(n) modulo 264.  

 

Sample Input 2 6 514  

 

Sample Output 26 328194  

 

Source 2015ACM/ICPC亞洲區長春站-重現賽(感謝東北師大)  
  • 要推公式啊,貼過程:

  • 註:
  • (1)後半個公式可以看做對於變數a在整數意義上的劃分,之後再進行gcd結果的加和。這裡對於劃分變數的方式有改進的餘地,可以根據gcd結果進行劃分。考慮gcd(x,a)|x,所以用x的因數對gcd結果進行劃分,而且最好用Dirichlet的形式進行改進,畢竟gcd和常函數都是積性函數,Dirichlet形式下的新函數保持積性函數的性質,利於簡化計算。
  • (2)對於f(x)的化簡結果,考慮帶入g(n)有進一步化簡的可能
  • (3)考慮整除的傳遞性,這裡如果可以把變數x消去是最好的。我們這裡先枚舉d,再找x,之後用i代替x/d,i*d|n,其中i*d==x,根據整除性質不難得到i|(d/n),那麼就看到一個很熟悉的公式,後半公式就是對於n求全部因數的歐拉函數,結果就是n本身
  • (4)最終結果
  • (5)把因數k次方和理解成多項式相乘處理是有一定好處的,好處在於沒有對於除法的處理,全都是簡單的加法和乘法,這對於取模運算是一大福音。此外,考慮到因數k次方函數是積性函數,也可以先對n分解質因數之後分步求解,但是這裡就要對於每一個質因數的乘方做等比數列求和,牽扯到除法,對應的在代碼中要做防溢出操作(好吧,我這個鶸是不會這種騷操作的QAQ)
  • 至於說題目里對於2^64取模就是在unsigned longlong下運算就ok

 

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 1e5 + 10   ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9 + 7    ;
20 const int    mxx  = 100 + 5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 ULL T, n, prime[maxn], nd, theta2;
25 bool vis[maxn];
26 int tot, cnt;
27 void init(int top){
28     tot=0;
29     memset(vis,true,sizeof(vis));
30     for(int i=2;i<=top;i++){
31         if(vis[i]){
32             prime[tot++]=(ULL)i;
33         }
34         for(int j=0;j<tot&&(i*prime[j]<=top);j++){
35             vis[i*prime[j]]=false;
36             if(i%prime[j]==0)
37                 break;
38         }
39     }
40 }
41 int main(){
42     // freopen("in.txt","r",stdin);
43     // freopen("out.txt","w",stdout);
44     init(1e5+1);
45     while(~scanf("%llu",&T)){
46         while(T--){
47             scanf("%llu",&n);
48             theta2=1ULL;
49             nd=n;
50             for(int i=0;i<tot && prime[i]*prime[i]<=n;i++)
51                 if(n%prime[i]==0){
52                     ULL p=prime[i], alpha=0ULL;
53                     ULL sigma=1ULL, square=1ULL;
54                     while(n%p==0ULL){
55                         alpha++;
56                         square*=p;
57                         sigma+=square*square;
58                         n/=p;
59                     }
60                     nd*=alpha+1ULL;
61                     theta2*=sigma;
62                 }
63             if(n>1){
64                 nd*=2ULL;
65                 theta2*=(1ULL+n*n);
66             }
67             printf("%llu\n",theta2-nd);
68         }
69     }
70     return 0;
71 }

 

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 首先我們知道了HTML和css用途,那麼今天就來看看HTML的一部分功能和用途。 簡單的說HTML就是靈活使用標簽,標簽就相當於一個網頁的骨架,有了這個骨架才能使網頁更能區域色彩化。 首先來說HTML術語 1.HTML文檔由許多個元素組成,所有的內容都是靠元素組織到頁面中。 2.元素的組成部分,簡單 ...
  • 寫在前面整個項目都托管在了 Github 上:https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp這一節內容可能會用到的庫文件有 Measurement 和 TestCase,同樣在 Github 上可以找到。善用 Ctrl + F... ...
  • 感覺又幫 Windows 10 IoT 開荒了,所以呢,正兒八經的寫篇博客吧。其實大概半年前就想寫的,那時候想做個基於 Windows 10 IoT 的小車,但樹莓派原生不支持 PWM 啊。百度也搜不到,上 GitHub 轉了一圈,在 @ms-iot 那發現了 Lightning ,再看最後的更新時 ...
  • 最近項目中需要一個導出Excel報告的功能,假期搜了一下,把其中比較主流的列一下,僅供參考。 功能需求: 效果圖: 一、ClosedXML 主頁:https://github.com/ClosedXML/ClosedXML 需要引用OpenXMLSDK(DocumentFormat.OpenXml. ...
  • <!ATTLIST 元素名 屬性名稱 屬性類型 屬性特點> 1.屬性類型 屬性值引用已定義的id值,複數形式可以應用多個id, 以空格隔開 (1)CDATA e.g (2) ID類型 (3)IDREF,IDREFS (4)enumerated枚舉類型 2.屬性特點 ...
  • Almost Sorted Array Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 6019 Accepted Submission(s) ...
  • 1.元素聲明 (1)any元素類型 <!ELEMENT 元素名 ANY> (2)EMPTY元素類型 <!ELEMENT 元素名 EMPTY> 空標記,即元素中沒有內容,不能包含子元素和文本 <person name="" age="" /> (3) PCDATA類型的元素(純文本) <!ELEMEN ...
  • 這一節主要介紹List介面的幾個實現類的區別: 1.線程安全 Vector是線程安全的,而ArrayList和LinkedList是非線程安全的。從源碼中我們可知,Vector類中的方法大部分都是同步的,即被synchronized關鍵字修飾;而那些沒有被synchronized關鍵字修飾的方法都是 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...