Count a * b 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 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

转载

 

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define per(i,a,b) for(int i=b-1;i>=a;--i)

const int N=1e5+10;
int cnt=0;
ULL  prime[N];
bool vis[N];
void init(int N)
{
    cnt=0;
    for(int i=2; i<N; i++) {
        if(!vis[i]) prime[cnt++]=i;
        for(int j=0; j<cnt&&i*prime[j]<N; j++) {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}

int main()
{
    init(1e5+1);
    int T;
    //scanf("%d",&T);
    scanf("%d",&T);
    while(T--) {
        ULL tmp,n;
        scanf("%llu",&n);
        //read(n);
        tmp=n;
        LL ans1=1,ans2=n;
        for(int i=0; i<cnt&&prime[i]*prime[i]<=n; i++) {
            if(n%prime[i]!=0)continue;
            ULL num=0,base=1,sum=1;
            while(n%prime[i]==0) {
                n/=prime[i];
                num++;
                base*=prime[i];
                sum+=base*base;
            }
            ans1*=sum;
            ans2*=(num+1);
        }
        if(n>1) {
            ans2*=2ULL;
            ans1*=(1ULL*n*n+1ULL);
        }
        printf("%llu\n",ans1-ans2);
    }
    return 0;
}