sunacm's blog

By sunacm, 10 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it