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 m≠0.
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.
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
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
- 要推公式啊，贴过程：
- 注：
- （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("%llun",theta2-nd); 68 } 69 } 70 return 0; 71 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
