### sunacm's blog

By sunacm, 9 years ago,

because i will take part in regional soon,recently i take some asia regional for practice,and i will write problem solution to make clear

first i will say this problem:The Boss on Mars

first we need to cal the sum of the sigma(i^4)

use polygen is easy to get,second,we need to delete the no coprime number. this will use the rongchi (in chinese 容斥） to solve,can solve in dfs easily

problem link:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=60895#problem/I there is the code:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <math.h>
#include <map>
#include <vector>

using namespace std;

typedef long long ll;

const ll mod=1000000007;

vector<ll>  yinzi;

ll pow_mod(ll aa,ll p)
{
ll temp=1;
ll a=aa;
int cnt=0;
while(p)
{
if((1<<cnt)&p)
{
temp=temp*a%mod;
p-=(1<<cnt);
}
a=a*a%mod;
cnt++;
}
return temp;
}

ll ni=pow_mod(30,mod-2);

bool isprime[100100];
ll prime[100100];

ll get(ll n)
{

ll a1=6*(n*n%mod)*(n*n%mod)%mod*n%mod;
ll a2=15*n%mod*n%mod*(n+1)%mod*(n+1)%mod;
ll a3=10*n%mod*(n+1)%mod*(2*n+1)%mod;
ll a4=15*n%mod*(n+1)%mod;
ll a5=6*n%mod;
ll ans=(a1+a2-a3+a4-a5)%mod;

return ans*ni%mod;

}

int cnt=0;

void getprime()
{

memset(isprime,true,sizeof(isprime));

for(int i=2;i<=10000;i++)
{
if(isprime[i])
{
for(int j=i*2;j<=10000;j+=i)
{
isprime[j]=false;

}
}
}

for(int i=2;i<=10000;i++)
{
if(isprime[i])
{
prime[cnt++]=(ll)i;
}

}

}

void getfactor(ll n)
{
yinzi.clear();
for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++)
{
if(n%prime[i]==0)
{
yinzi.push_back(prime[i]);
while(n%prime[i]==0)
n/=prime[i];
}

}
if(n>1)
yinzi.push_back(n);
}

ll dfs(int i,ll n)
{
ll tt=0;
for(int p=i;p<yinzi.size();p++)
{
tt=(tt+get(n/yinzi[p])*pow_mod(yinzi[p],4)%mod)%mod;
tt=(tt-dfs(p+1,n/yinzi[p])*pow_mod(yinzi[p],4)%mod+mod)%mod;
}
return tt%mod;

}

void solve(ll n)
{

getfactor(n);
ll ans1=dfs(0,n);
ll ans2=get(n);
ll ans=((ans2-ans1)%mod+mod)%mod;

cout<<ans<<endl;

}

int main()
{
int T;
scanf("%d",&T);
getprime();

while(T--)
{
ll n;
cin>>n;
solve(n);

}

return 0;
}


• +7

 » 9 years ago, # |   0 i will update when i solve new question