小说网站怎么做流量,wordpress微信个人支付,vr网站开发,网站会员注册系统源码题目大意#xff1a;
ACM 有 n 名员工#xff0c;现在是他们从老板那里拿薪水的时候了。所有员工都从 1 到 n 编号。原因不明#xff0c;如果员工的工作编号是 k#xff0c;他今年可以获得 k^4 Mars 美元。所以为 ACM 工作的员工非常富有。
因为员工人数太多#xff0c;…
题目大意
ACM 有 n 名员工现在是他们从老板那里拿薪水的时候了。所有员工都从 1 到 n 编号。原因不明如果员工的工作编号是 k他今年可以获得 k^4 Mars 美元。所以为 ACM 工作的员工非常富有。
因为员工人数太多ACM 的老板必须分配太多的钱他想明年解雇工作号与 n 共质的人。现在老板想知道解雇后他会节省多少钱。 思路先求出1~n的每个数的四次方的求和然后再减去n的因子的四次方的求和。把n的因子的质因子找出来然后使用容斥原理我容斥原理用的方法是二进制去做。
求和公式 ( 搜来的 ) 代码如下
#includebits/stdc.h
using namespace std;
#define int long long
const int mod1e97;
int vis[10005],prime[10005];
int ksm(int x,int y){int ans1;while(y){if(y1) ansans*x%mod;xx*x%mod;y1;}return ans;
}
int fun(int x){//求 a ^ 4 的前 x 项和return (x*(x1)%mod*(2*x1)%mod*(3*x*x%mod3*x%mod-1mod)%mod)%mod*ksm(30,mod-2)%mod;
}
signed main(){int cnt0;for(int i2;i10000;i){//埃式筛求 1 ~ 10000 之间的素数 if(vis[i]) continue;prime[cnt]i;for(int ji*2;j10000;ji){vis[j]1;}}int _;cin _;while(_--){int n;cin n;vectorint v;//存质因数 int mn;for(int i0;icnt;i){//挑选 n 的质因子 if(m%prime[i]0){v.push_back(prime[i]);while(m%prime[i]0) m/prime[i];}}if(m1) v.push_back(m);//若不为 1 说明还留下 1 个质因子 int ansfun(n),res0;for(int i1;i(1v.size());i){int num1,sum0;//num 代表几种不同质因子组成的最小因子 sum 代表质因子的个数 for(int j0;jv.size();j){ if((ij)1) sum,num*v[j];}int tmpnum*num%mod*num%mod*num%mod*fun(n/num);//求出 num 的倍数(不大于 n ) 的四次方之和。将这个最小因子的四次方之和提出剩下的就是 a^4 的前几项和//例如2^4 4^4 6^4 8^4 2^4 * ( 1^4 2^4 3^4 4^4 )if(sum%2) res(restmp)%mod;//容斥原理 else res(res-tmp)%mod;}ans((ans-res)%modmod)%mod;cout ans endl;}return 0;
}
