HDU 5528 Count a × b 数论

Count a * b Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1571Accepted Submission(s): 523

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 .
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

这道题就是求
HDU 5528 Count a × b

文章图片

文章图片

推到这一步,然后就有了一种sqrt(n)的解法
然而T=20000
于是成功卡常
参考唯一分解定理

于是现在可以先筛一个素数表
复杂度sqrt(n)以内的质数sqrt(n)/ln(n)
比上一种方法快几倍
这道题时间卡得很紧
HDU 5528 Count a × b

文章图片

然而，成功爆unsigned long long

在这里，
引入__int128成功卡过

网上还有其他的防止溢出的方法

#include using namespace std; typedef unsigned long long ull; const int MAX=100010; long long su[MAX],cnt; bool isprime[MAX]; void prime() { cnt=1; memset(isprime,1,sizeof(isprime)); isprime[0]=isprime[1]=0; for(long long i=2; i<=MAX; i++) { if(isprime[i]) su[cnt++]=i; for(long long j=1; jn) break; int k=0; ull tp=su[i]; while(n%su[i]==0) { k++; tp*=su[i]; n/=su[i]; } //tp=tp*tp-1; if(k) { io=(__int128)tp*tp-1; //爆ull ans1=ans1*(ull)(io/((ull)su[i]*su[i]-1)); ans2=ans2*(k+1); } } if(n!=1) { ans1=ans1*((ull)n*n+1); ans2=ans2*2; } printf("%llu\n",ans1-ans2); } return 0; }

【HDU 5528 Count a × b】