hdu5528Count a * b（数论）

题目链接https://cn.vjudge.net/problem/HDU-5528

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 mm, 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 nn. Your task is to find g(n) modulo 2^64.

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

1≤T≤20000
1≤n≤10^9

Output

For each test case, print one integer ss, representing g(n) modulo 2^64.

Sample Input

2
6
514

Sample Output

26
328194

听说结果没有大于等于2^64的，直接用long long算？？？

推导见大神博客https://blog.csdn.net/Coldfresh/article/details/82189233

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int N=4e4+5;
bool p[N];
int prime[N],cnt=0; 
void init(){
	p[0]=p[1]=true;
	for(int i=2;i<N;i++){
		if(!p[i]) prime[cnt++]=i;
		for(int j=0;j<cnt&&(ll)i*prime[j]<N;j++){
			p[i*prime[j]]=true;
			if(i%prime[j]==0) break;
		}
	}
}
int fac[50],e[50];
ll k,ans;
void getFac(int x){        //唯一分解 
	k=0;
	for(int i=0;i<cnt&&x!=1;i++){
		if(x%prime[i]==0){
			fac[k]=prime[i];
			e[k]=0;
			while(x%prime[i]==0){
				x/=prime[i];
				e[k]++;
			}
			k++;
		}
	}
	if(x!=1){
		fac[k]=x;
		e[k]=1;
		k++;
	}
}
void dfs(int pos,ll temp){ //dfs枚举因子 
	if(pos==k){
		ans+=temp*temp;
		return ;
	}
	dfs(pos+1,temp);
	ll t=temp;
	for(int i=1;i<=e[pos];i++){
		t*=fac[pos];
		dfs(pos+1,t);
	}
}
ll solve(int x){
   getFac(x);
   ll a=1;
   for(int i=0;i<k;i++){
   	   a*=e[i]+1;
   }
   ans=0-a*x;
   dfs(0,1);
   return ans;
}
int main(){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
    	int x;
    	scanf("%d",&x);
    	printf("%lld\n",solve(x));
	}
	return 0;
}