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;
}