P6523 「Wdoi-1」加密通信题目背景自月战之后八云紫在槐安通道中设立了一重结界使得从地面传向月都的信息全部会被拦截和破译。为了维持正常的通讯八意永琳同月兔们研究出了一种全新的加密方式。题目描述首先八意永琳会写出需要被加密的明文A AA此段明文由n − 1 n-1n−1个正整数构成。之后她会构造出一个由n nn个质数构成的密文B BB满足对∀ i ∈ [ 1 , n ) , B i × B i 1 A i \forall i \in [1,n),B_i \times B_{i 1} A_i∀i∈[1,n),Bi​×Bi1​Ai​。为了提高信息的利用率八意永琳规定B BB中出现的所有质数的值必须在[ 1 , M ] [1,M][1,M]范围内。输入格式第一行一个整数T TT, 表示需要被加密的明文的组数。对于每组明文第一行两个整数n , M n,Mn,M代表明文的长度 1 11也即所求密文的长度和可出现质数的最大值。接下来一行n − 1 n - 1n−1个由空格隔开的正整数代表明文A AA。输出格式对于每组明文均输出一行若有解输出任意一组合法密文B BB即可密文中的n nn个质数以空格隔开。若无解输出-1。输入输出样例 #1输入 #12 4 233 55 35 77 4 5 55 35 77输出 #111 5 7 11 -1说明/提示数据规模对于20 % 20\%20%的数据n ≤ 5 , M ≤ 10 n \le 5,M \le 10n≤5,M≤10。对于40 % 40\%40%的数据A i ≤ 10 12 A_i \le 10 ^ {12}Ai​≤1012。对于70 % 70\%70%的数据A i ≠ A i 1 A_i \neq A_{i 1}Ai​Ai1​。对于100 % 100\%100%的数据3 ≤ n ≤ 10 5 3 \le n \le 10 ^ 53≤n≤1051 ≤ A i , M ≤ 10 18 1 \le A_i,M \le 10 ^ {18}1≤Ai​,M≤10181 ≤ T ≤ 5 1 \le T \le 51≤T≤5。以上几档部分分呈包含关系100 % 100\%100%包含70 % 70\%70%70 % 70\%70%包含40 % … … 40\%\ \ldots\ldots40%……以此类推。数据保证若不考虑b i b_ibi​在[ 1 , M ] [1,M][1,M]范围内的条件必然有至少一组合法解。有至少一对( i , j ) (i,j)(i,j)使得A i ≠ A j A_i \neq A_jAi​Aj​。后置资料本段资料与答题相关性不大。百度百科 - 质数C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;constintM1e510;intT;inta[M],ans[M];intgcd(inta,intb){returnb0?a:gcd(b,a%b);}//求最大公因数inlineintread(){charcgetchar();intx0;boolf0;for(;!isdigit(c);cgetchar())f^!(c^45);for(;isdigit(c);cgetchar())x(x1)(x3)(c^48);if(f)x-x;returnx;}signedmain(){Tread();while(T--){memset(a,0,sizeof(a));memset(ans,0,sizeof(ans));intnread(),mread(),ooo;for(inti1;in;i)a[i]read();for(inti1;in-1;i)if(a[i]!a[i1]){intkgcd(a[i],a[i1]);ans[i1]k,oooi1;break;}for(intjooo-1;j1;j--)ans[j]a[j]/ans[j1];//向前推密文for(intjooo1;jn;j)ans[j]a[j-1]/ans[j-1];//向后推密文intflag1;for(inti1;in;i)if(ans[i]m){flag0;break;}//判断是否有质数大于mif(!flag)printf(-1\n);elsefor(inti1;in;i)printf(%lld ,ans[i]);printf(\n);//输出}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容