首页 > > 程序设计 > C/C++ >

HDU_5528_Count a * b

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

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

Input

The first line contains an integer

Output

For each test case, print one integer

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 }