傳送門 歐拉函數(shù)都會求的吧。 首先給出一個結(jié)論：做一次phi只會消去一個2（自己yy） 設(shè)奇數(shù)x能分解產(chǎn)生f[x]個二，則消去他要f[x]+1次。 f[x]是積性函數(shù)（自己yy），可以O(shè)(N)求出。 當(dāng)然，當(dāng)開始是奇數(shù)時，還要再多一次 求一下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; }新聞熱點(diǎn)
疑難解答
