HDu 3501(反発原理)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3501;
題意:nとnの非互質の数の和より小さい数nの解を与える.
解析:明らかな反発原理は,n素因子を分解した後,奇数因子の数の和に偶数個を加えて減算すればよい.(2を割り切れる数より小さい和は2*(1+n/2)*n/2*2);
コードは次のとおりです.

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <math.h>
#include <string>
#include <stdio.h>
#include <iostream>
using namespace std;
long long fac[500];
int cnt;
void fen(int n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            fac[cnt++]=i;
            while(n%i==0)n/=i;
        }
    }
    if(n>1)fac[cnt++]=n;
}//     
long long ans;
int n;
const int mod=1000000007;
void dfs(int w,int id,long long sum){
    for(int i=w;i<cnt;i++){
        long long ss=sum*fac[i];
        if(id&1){
            int tmp=n/ss;
            ans+=ss*(1+tmp)*tmp/2;
            ans%=mod;
        }
        else{
            int tmp=n/ss;
            ans-=ss*(1+tmp)*tmp/2;
            ans=(ans+mod)%mod;
        }
        dfs(i+1,id+1,ss);
    }
}//        
int main(){
    while(scanf("%d",&n)!=EOF){
        if(n==0)break;
        if(n==1){
            cout<<0<<endl;
            continue;
        }
        cnt=0;
        fen(n);
        ans=0;
        dfs(0,1,1);
        cout<<(ans%mod-n+mod)%mod<<endl;
    }
    return 0;
}