正題

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

---

題目大意

$n$的所有約數(shù)排成一個圈，求一個順序使得相鄰的互質(zhì)的數(shù)最少。

---

解題思路

質(zhì)因數(shù)分解后，我們考慮每個質(zhì)因數(shù)之間填什么。對于兩個質(zhì)因數(shù)$a,b$。顯然$a?b$也是$n$的約數(shù)，也就是$a$與$b$之間必定有一個可以填進(jìn)去的數(shù)。

顯然對于每個質(zhì)因數(shù)也是如此，一般的，我們對于分解出來的$p^c$和$p^{\prime c^{\prime }}$我們可以在將$p^k(1\le k\le c)$都填在一起，然后在之后填上具有$p$和$p^{\prime }$因子的所有沒有填過的約數(shù)。特別的，$n$要填在最后面（拼接第一個和最后一個質(zhì)因子）。

然后對于只有兩個不同的質(zhì)因子$a,b$的數(shù)，我們不難發(fā)現(xiàn)$a?b=n$也就是$n$沒有辦法填在最后，此時互質(zhì)數(shù)為$1$，其他都為$0$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=2e5+10; ll T,n,p[N],v[N],cnt; void dfs(ll dep,ll x){if(x==n||dep>cnt&&x==1)return;if(dep>cnt){printf("%lld ",x);return;}ll w=p[dep],z=1;if(x==1){for(ll i=1;i<=v[dep];i++)z*=w;for(ll i=v[dep];i>=0;i--)dfs(dep+1,x*z),z/=w;}else{for(ll i=0;i<=v[dep];i++)dfs(dep+1,x*z),z*=w;} } int main() {scanf("%lld",&T);while(T--){scanf("%lld",&n);ll x=n,z=0;cnt=0;for(ll i=2;i*i<=x;i++){if(x%i==0){p[++cnt]=i;while(x%i==0)x/=i,v[cnt]++,z++;}}if(x!=1){bool flag=1;for(ll i=1;i<=cnt;i++)if(p[i]==x){flag=0;break;}if(flag){p[++cnt]=x;v[cnt]++;z++;}}dfs(1,1);printf("%lld\n",n);if(z==2&&cnt==2)printf("1\n");else printf("0\n");for(ll i=1;i<=cnt;i++)v[i]=0;} }

總結(jié)

以上是生活随笔為你收集整理的CF1419E-Decryption【数论,dfs】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。