正題

題目鏈接:https://www.luogu.com.cn/problem/P2350

---

題目大意

給出$N$質因數分解之后的結果，求每次$N=\phi (N)$，多少次后$N=1$。

$N={\prod }_{i=1}^m{p}_i^{q_i},1\le m\le 2000,1\le p_i\le 10^5,1\le q_i\le 10^9$

---

解題思路

我是傻逼（（（（

首先$\phi ({\prod }_{i=1}^m{p}_i^{q_i})={\prod }_{i=1}^m(p_i?1)p_i^{q_i?1}$
開始想太多了，以為傳遞的延遲影響很大，后來發現設因為$p_i?1$一定是偶數，所以把$p_i?1$分解后一定有$2$這個質因子，所以只有在$N$沒有$2$這個質因子的情況下傳遞的延遲會造成一次的影響，否則都沒有影響，因為$2$還沒有抵消延遲就已經結束了。

所以我們只需要考慮每個質數能傳遞出多少個$2$，這個用線性篩可以解決因為最后更新一個質數的一定是新增的一個質因子。

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10,M=1e5+10; int T,n,cnt,pri[N],f[M],v[M]; void Prime(){f[1]=1;for(int i=2;i<M;i++){if(!v[i])pri[++cnt]=i,f[i]=f[i-1];for(int j=1;j<=cnt&&i*pri[j]<M;j++){v[i*pri[j]]=1;f[i*pri[j]]=f[i]+f[pri[j]];if(i%pri[j]==0)break;}}return; } int main() {Prime();scanf("%d",&T);while(T--){scanf("%d",&n);if(!n)puts("0");long long ans=1;for(int i=1;i<=n;i++){int x,w;scanf("%d%d",&x,&w);if(x==2)ans--;ans+=1ll*f[x]*w;}printf("%lld\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的P2350-[HAOI2012]外星人【线性筛】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。