題目鏈接：點(diǎn)擊查看

題目大意：給出兩個(gè)數(shù)組，數(shù)組a表示的是分子的因數(shù)，數(shù)組b表示的是分母的因數(shù)，求約分后的答案

題目分析：一看題目挺簡(jiǎn)單的，但是在輸出的那里這個(gè)題目做了特定的要求，題目首先給出的是1e5個(gè)數(shù)，每個(gè)數(shù)最大到1e7，然后輸出的時(shí)候最多只能輸出1e5個(gè)數(shù)，每個(gè)數(shù)最大也只能到1e7，這就導(dǎo)致了我們無(wú)法構(gòu)造答案，本來(lái)我想的是用兩個(gè)1e7的sum數(shù)組分別記錄分子和分母的所有素因子，最后一起輸出即可，因?yàn)?是最小的素?cái)?shù)，所以一個(gè)不超過(guò)1e7的數(shù)，最多只能拆成20個(gè)素?cái)?shù)，而1e5個(gè)數(shù)最多只能拆成2e6個(gè)數(shù)，并不是很大，一開(kāi)始這樣寫(xiě)了一發(fā)，交上去WA掉了，原因就是輸出超過(guò)限制長(zhǎng)度了，所以這個(gè)題需要換一種思考方式，因?yàn)檩斎牒洼敵龅臄?shù)量還有大小關(guān)系都非常相似，那么我們能不能直接在原數(shù)組上進(jìn)行約分呢？多余的都視作1就行了，經(jīng)過(guò)zx學(xué)長(zhǎng)的提醒后，我嘗試性的寫(xiě)了一發(fā)，沒(méi)想到還真的給過(guò)了。。

大概就是運(yùn)用兩次唯一分解定理吧，第一次用到的時(shí)候是中規(guī)中矩的分解素因子，這里我一開(kāi)始打了一個(gè)1e5的素?cái)?shù)表用來(lái)加速分解的整個(gè)過(guò)程，第二次用到的時(shí)候就是約分了，對(duì)于其中的一些細(xì)節(jié)進(jìn)行了改動(dòng)，具體的看代碼吧，這個(gè)題目也可以算做一個(gè)小模擬，所以看代碼比看文字說(shuō)明要清晰多了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef unsigned long long ull;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int pri[N];int cnt=0;bool vis[N];int a[N],b[N];int sum1[10000000],sum2[10000000];//儲(chǔ)存素因子void P()//歐拉線性篩 {for(int i=2;i<N;i++){if(!vis[i])pri[cnt++]=i;for(int j=0;j<cnt&&pri[j]*i<N;j++){vis[pri[j]*i]=true;if(i%pri[j]==0)break;}} }void only(int sum[],int x)//中規(guī)中矩的唯一分解定理 {for(int i=0;i<cnt&&pri[i]*pri[i]<=x;i++){if(x%pri[i]==0){while(x%pri[i]==0){x/=pri[i];sum[pri[i]]++;//在數(shù)組中出現(xiàn)的次數(shù)加一}}if(x==1)break;}if(x>1)sum[x]++; }void del(int sum[],int& x) {int temp=1;//記錄當(dāng)前的值，最后會(huì)還給xfor(int i=0;i<cnt&&pri[i]*pri[i]<=x;i++){if(x%pri[i]==0){while(x%pri[i]==0){x/=pri[i];if(sum[pri[i]])//若該因子在分子或分母中出現(xiàn)了，即可以約分sum[pri[i]]--;else//若沒(méi)出現(xiàn)，或者已經(jīng)被約沒(méi)了，就要在原來(lái)的地方保留，即乘上就行temp*=pri[i];}}if(x==1)break;}if(x>1){if(sum[x])sum[x]--;elsetemp*=x;}x=temp;//將儲(chǔ)存的值還給x }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);P();//打個(gè)素?cái)?shù)表int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)//讀入分子，將其唯一分解到sum1中{scanf("%d",a+i);only(sum1,a[i]);}for(int i=1;i<=m;i++)//讀入分母，將其唯一分解到sum2中{scanf("%d",b+i);only(sum2,b[i]);}for(int i=1;i<=n;i++)//用分母對(duì)sum1約分del(sum2,a[i]);for(int i=1;i<=m;i++)//用分子對(duì)sum2約分del(sum1,b[i]);printf("%d %d\n",n,m);//最后原樣輸出for(int i=1;i<=n;i++)printf("%d ",a[i]);printf("\n");for(int i=1;i<=m;i++)printf("%d ",b[i]);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 222C Reducing Fractions(唯一分解定理)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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