hdu 45092011年大連現場試合I題(反発原理)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=4059; 題意:nとnの互質の数より小さい四次方和を求める.分析:まず四次方程式と公式を解いて、簡単に押します.
必ず4次方程式の求和式を用いなければならない.次に簡単に証明すると、ここでは3回の方程式の公式を知っていることを前提として、次のパターンに従って2回の公式を利用して3回の公式(x+1)^5=x^5+5*x^4+10*x^3+10*x^3+10*x^2+5*x+1;1=1;2=1;2^5=(1+1)^5=1^5+5+5*1^4+10*1^3+10*1^3+10*1^0*1^2+1;3^5=(2+1)^5=(5=2^4+10*2+10*2+10*2+2+2+2*2+5*2+5*2+5*2*2+2*2*2......(n+1)^5=(n+1)^5=n^5+5*n^4+10*n^3+10*n^2+n^2+5*n^1+1;すべて重ね合わせると(n+1)^5=5*(1^4+2^4+・・・・n^4)+10*(1^3+2^3+・・・+n^3)+10*(1^2+2^2+・・・+n^2)+5*(1+2+2+・・・+n)+n+1;そして(1^3+2^3+2^3+・・・・・n^4)=(n+1)^2*n^2*2 2/4;(1^2+2+2+2+n^2+・・・・・・・・・・・・・・・・)=(n*(n+1)*(2*n+1))/6;代入.簡略化後(1^4+2^4+......+n^4)=(n*(n+1)*(2 n+1)*(3*n*n+3*n-1))/30;
それから30の逆元を解くことです.私は手で計算しました...普通は1回拡張ユークリッドでいいです.
nとの互質の数については,まずnとの非互質の数を求め,その素因子の倍数と素因子積の倍数である.ここでは反発で解く.
反発原理の詳細は、反発原理;
コードは次のとおりです.

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <vector>
#include <string>
#include <utility>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;
long long ans;
const long long mod=1000000007;
const long long maxn=50;
long long fac[maxn];
long long cnt;
void fen(long long n){
    for(long long i=2; i*i<=n; i++){
        if(n%i==0){
            fac[cnt]=i;
            while(n%i==0)n/=i;
            cnt++;
        }
    }
    if(n>1)fac[cnt++]=n;
}//     
void dfs(long long id,long long k,long long w,long long sumsum){
    if(id==cnt+1)return;
    long long temp;
    for(long long i=w;i<cnt;i++){
        temp=sumsum*fac[i];
        long long m=k/temp;
        long long tmp=(m*(m+1))%mod;
        tmp=(tmp*(2*m+1))%mod;
        tmp=(tmp*(3*m*m%mod+3*m%mod-1+mod))%mod;
        tmp=((tmp*233333335ll)%mod+mod)%mod;
        tmp=(tmp*((((temp*temp%mod)*temp%mod)*temp)%mod))%mod;
        if(id&1)ans=((ans-tmp)%mod+mod)%mod;
        else ans=(ans+tmp)%mod;
        dfs(id+1,k,i+1,temp%mod);
    }
}//        
int main()
{
    long long t;
    scanf("%I64d",&t);
    while(t--){
        long long n;
        scanf("%I64d",&n);
        cnt=0;
        fen(n);
        ans=(n*(n+1))%mod;
        ans=(ans*(2*n+1))%mod;
        ans=(ans*(3*n*n%mod+3*n%mod-1+mod))%mod;
        ans=((ans*233333335ll)%mod+mod)%mod;
        dfs(1,n,0,1);
        printf("%I64d
",(ans%mod+mod)%mod);
    }
    return 0;
}