HDU_5528_Count a * b

2018-06-17 21:49:00来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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 }

 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:hihoCoder_1449_后缀自动机三&#183;重复旋律6

下一篇:memset函数及注意事项