传送门 欧拉函数都会求的吧。 首先给出一个结论：做一次phi只会消去一个2（自己yy） 设奇数x能分解产生f[x]个二，则消去他要f[x]+1次。 f[x]是积性函数（自己yy），可以O(N)求出。 当然，当开始是奇数时，还要再多一次 求一下sigma就行了。
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<algorithm>#define N 100005#define ll long longusing namespace std;int n,m,x,y,cnt,cas,f[N],c[N];int main(){ f[1]=1; for (int i=2;i<N;i++){ if (!f[i]) c[++cnt]=i,f[i]=f[i-1]; for (int j=1;j<=cnt&&i*c[j]<N;j++){ f[i*c[j]]=f[i]+f[c[j]]; if (i%c[j]==0) break; } } scanf("%d",&cas); while (cas--){ scanf("%d",&n); int flag=1; ll ans=0; for (int i=1;i<=n;i++){ scanf("%d%d",&x,&y); flag&=x&1; ans+=(ll)f[x]*y; } PRintf("%lld/n",ans+(ll)flag); }}新闻热点
疑难解答
