HDU——5528 Count a * b(积性函数推公式+唯一分解定理) 数论

Marry likes to count the number of ways to choose two non-negative integers aa and bbless than mm to make a×ba×b mod m≠0m≠0.

Let's denote f(m)f(m) as the number of ways to choose two non-negative integers aa and bbless than mm to make a×ba×b mod m≠0m≠0.

She has calculated a lot of f(m)f(m) for different mm, and now she is interested in another function g(n)=∑m|nf(m)g(n)=∑m|nf(m). For example, g(6)=f(1)+f(2)+f(3)+f(6)=0+1+4+21=26g(6)=f(1)+f(2)+f(3)+f(6)=0+1+4+21=26. She needs you to double check the answer.

Give you nn. Your task is to find g(n)g(n) modulo 264264.
Input
The first line contains an integer TT indicating the total number of test cases. Each test case is a line with a positive integer nn.

1≤T≤200001≤T≤20000
1≤n≤1091≤n≤109
Output
For each test case, print one integer ss, representing g(n)g(n) modulo 264264.
Sample Input

2 6 514

Sample Output

26 328194

题意：求

文章图片
（|是整除，（!|）是不整除，因为不会弄这个符号）括号（断言）里的意思是，如果i*j%x==0 返回0，否则返回1
题解：推导公式：我写了纸上了~~
请看：
化简f(m):

文章图片

化简g(n):

文章图片

上代码：

#include #include using namespace std; typedef long long ll; const int MAX = 1e5+10; ll p[MAX]; bool vis[MAX]; int cnt; void init(){//筛素数 vis[1]=vis[0]=1; for (int i = 2; i < MAX; i++){ if(!vis[i]) p[cnt++]=i; for (int j = 0; j < cnt&&i*p[j] < MAX; j++){ vis[i*p[j]]=1; if(i%p[j]==0) break; } } } int main(){ init(); int t; scanf("%d",&t); while(t--){ ll n; scanf("%lld",&n); ll ans1,ans2; ans1=ans2=1; ll w=n; for (int i = 0; p[i]*p[i]<=n; i++){//唯一分解定理 ll a,b,c; a=b=c=1; while(n%p[i]==0){ a++; b*=p[i]; n/=p[i]; c+=b*b; } ans1*=c; ans2*=a; } if(n>1){ ans1*=(n*n+1ll); ans2*=2; } printf("%lld\n",ans1-ans2*w); } return 0; }

【HDU——5528 Count a * b(积性函数推公式+唯一分解定理)】