題目鏈接：點擊查看

題目大意：給出 n 個數，對于每個數而言，需要找出一個大于 1 的 d1 和 d2 ，滿足：

gcd( d1 + d2 , a[ i ] ) == 1

d1 和 d1 是 a[ i ] 的因子

如果不存在，輸出 -1 ， -1

題目分析：需要證明的一道題目

證明參考自：https://www.cnblogs.com/lr599909928/p/13110608.html

首先通過 gcd 的性質不難推出兩個結論：

gcd( a , b ) = gcd( a + b , b )

已知 gcd( a , b ) = 1 ， 則 gcd( a , bc ) = gcd( a , c )

根據上面兩個結論，得到推論：

gcd( a , b ) = 1 <=> gcd( a + b , ab ) = 1

這樣我們只需要對每個 a[ i ] 進行質因子分解，找到皆大于 1 的?d1 = p1^k ，d2 = a[ i ] / d1 即為答案

因為數據較大，所以需要預處理打表降低一下唯一分解定理的時間復雜度

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=5e5+100,M=1e7+100;int pri[M],cnt,n;bool vis[M];pair<int,int>ans[N];void P() {for(int i=2;i<M;i++){if(!vis[i])pri[cnt++]=i;for(int j=1;j<cnt&&pri[j]*i<M;j++){vis[pri[j]*i]=true;if(i%pri[j]==0)break;}} }void only() {for(int i=1;i<=n;i++){int num;scanf("%d",&num);int ans1=-1,ans2=-1;for(int j=0;j<cnt&&pri[j]*pri[j]<=num;j++){if(num%pri[j]==0){ans1=1;while(num%pri[j]==0){num/=pri[j];ans1*=pri[j];}ans2=num;if(ans1==1||ans2==1)ans1=ans2=-1;break;}}ans[i]=make_pair(ans1,ans2);} }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);P();scanf("%d",&n);only();for(int i=1;i<=n;i++)printf("%d ",ans[i].first);puts("");for(int i=1;i<=n;i++)printf("%d ",ans[i].second);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1366D Two Divisors(数论)的全部內容，希望文章能夠幫你解決所遇到的問題。

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