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
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 m≠0.
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.
1≤T≤20000
1≤n≤109
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 }
