Jennie

$c^nm=c^{n/p}{m/p}*{c^{n%p}_{m%p}}$

然后套上去就行了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
int prime[9000006];
int vis[9000005];
int sum[9000005];
int n;
int p;
void ini(){
    int nn=sqrt(n);
    for(int i=2;i<=nn;++i){
        if(!vis[i]){
            p++;
            prime[p]=i;
        }
        for(int j=1;j<=p&&i*prime[j]<=nn;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                break;
            }
        }
    }
}
int ans;
int phi(int x){
    int tem=x;
    for(int i=1;i<=p&&prime[i]*prime[i]<=x;++i){
        if(x%prime[i]) continue;
        tem=tem/prime[i]*(prime[i]-1);
        while(x%prime[i]==0) x/=prime[i];
    }
    if(x>1) tem=tem/x*(x-1);
    return tem;
}
signed main(){
    scanf("%d",&n);
    ini();
    for(int i=1;i*i<=n;++i){
        if(n%i==0){
            if(i*i!=n)
            ans+=i*phi(n/i)+(n/i)*phi(i);
            else
            ans+=i*phi(i);
        }       
    }
    cout<<ans;
    return 0;
}