2015
04-16

The Boss on Mars

On Mars, there is a huge company called ACM (A huge Company on Mars), and it’s owned by a younger boss.

Due to no moons around Mars, the employees can only get the salaries per-year. There are n employees in ACM, and it’s time for them to get salaries from their boss. All employees are numbered from 1 to n. With the unknown reasons, if the employee’s work number is k, he can get k^4 Mars dollars this year. So the employees working for the ACM are very rich.

Because the number of employees is so large that the boss of ACM must distribute too much money, he wants to fire the people whose work number is co-prime with n next year. Now the boss wants to know how much he will save after the dismissal.

The first line contains an integer T indicating the number of test cases. (1 ≤ T ≤ 1000) Each test case, there is only one integer n, indicating the number of employees in ACM. (1 ≤ n ≤ 10^8)

The first line contains an integer T indicating the number of test cases. (1 ≤ T ≤ 1000) Each test case, there is only one integer n, indicating the number of employees in ACM. (1 ≤ n ≤ 10^8)

2
4
5

82
354
Hint
Case1: sum=1+3*3*3*3=82
Case2: sum=1+2*2*2*2+3*3*3*3+4*4*4*4=354


http://acm.hdu.edu.cn/showproblem.php?pid=4059

（x+1)^5=x^5+5*x^4+10*x^3+10*x^2+5*x+1;

2^5=(1+1)^5=1^5+5*1^4+10*1^3+10*1^2+5*1^1+1;

3^5=(2+1)^5=2^5+5*2^4+10*2^3+10*2^2+5*2^1+1;

……

……

(n+1)^5=(n+1)^5=n^5+5*n^4+10*n^3+10*n^2+5*n^1+1;

http://blog.csdn.net/acm_cxlove/article/details/7422265

/*
ID:cxlove
PROB:HDU 4059
HINT:数论+容斥原理
DATA:2012.4.7
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define LL long long
#define MOD 1000000007
using namespace std;
LL res;  //30对MOD的逆元
int prime[10000],cnt=0,flag[10005]={0};
vector<int>fact;
LL PowMod(LL a,LL b){
LL ret=1;
while(b){
if(b&1)
ret=(ret*a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return ret;
}
LL Sum(LL n){ //求an=n^4,的前n项和
LL ans=n;
ans=(ans*(n+1))%MOD;
ans=(ans*((2*n+1)%MOD))%MOD;
ans=(ans*(((3*n*n)%MOD+(3*n)%MOD-1+MOD)%MOD))%MOD;
ans=(ans*res)%MOD;
return ans;
}
LL Pow(LL n){ //求n^4
LL ans=n;
ans=(((((ans*n)%MOD)*n)%MOD)*n)%MOD;
return ans;
}
int t;
void Prime(){  //筛选素数，便于后面的分解
for(int i=2;i<=10000;i++){
if(flag[i]) continue;
prime[cnt++]=i;
for(int j=2;j*i<=10000;j++)
flag[i*j]=1;
}
}
void Init(){
res=PowMod(30,MOD-2);   //求30对MOD的逆元
Prime();
scanf("%d",&t);
}
LL dfs(int idx,LL n){    //容斥原理
LL ret=0,tmp;
for(int i=idx;i<fact.size();i++){
tmp=fact[i];
ret=(ret+(Sum(n/tmp)*Pow(tmp))%MOD)%MOD;
ret=((ret-dfs(i+1,n/tmp)*Pow(tmp))%MOD+MOD)%MOD;
}
return ret%MOD;
}
int main(){
LL n;
Init();
while(t--){
scanf("%I64d",&n);
fact.clear();
LL tmp=n;
for(int i=0;i<cnt&&prime[i]<=tmp;i++)
if(tmp%prime[i]==0){
fact.push_back(prime[i]);
while(tmp%prime[i]==0)
tmp/=prime[i];
}
if(tmp!=1)
fact.push_back(tmp);
LL sum=((Sum(n)-dfs(0,n))%MOD+MOD)%MOD;
printf("%I64d\n",sum);
}
return 0;
}


1. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

2. [email protected]