P10827 [EC Final 2020] Square题目描述Father Study 非常喜欢数学。给定一个整数序列a1,a2,...,ana_1,a_2,...,a_na1​,a2​,...,an​Father Study 想要计算另一个整数序列t1,t2,...,tnt_1,t_2,...,t_nt1​,t2​,...,tn​满足以下条件对于每个i (1≤i≤n)i~(1 \le i \le n)i(1≤i≤n)有ti0t_i 0ti​0。对于每个i (1≤in)i~(1\le i n)i(1≤in)ai×ti×ai1×ti1a_i \times t_i \times a_{i1} \times t_{i1}ai​×ti​×ai1​×ti1​是一个完全平方数。在数学中完全平方数是一个整数它是某个整数的平方换句话说它是某个整数与其自身的乘积。∏i1nti\prod_{i1}^{n}{t_i}∏i1n​ti​的值最小。请帮助 Father Study 计算答案即∏i1nti\prod_{i1}^{n}{t_i}∏i1n​ti​的最小值。由于答案可能过大请输出答案对100000000710000000071000000007取模的结果。输入格式第一行包含一个整数nnn(1≤n≤1000001\le n \le 1000001≤n≤100000)。第二行包含nnn个整数a1,a2,...,ana_1, a_2, ..., a_na1​,a2​,...,an​(1≤ai≤10000001 \le a_i \le 10000001≤ai​≤1000000)它们由单个空格分隔。输出格式输出一个整数即答案对100000000710000000071000000007取模的结果。输入输出样例 #1输入 #13 2 3 6输出 #16说明/提示由 ChatGPT 4o 翻译C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN1e610;constintmod1e97;intn,ans1,a[N],cnt[N];mapint,intmp[N];boolisp[N];intksm(inta,intb,intc){if(b0)return1%c;if(b1)returna%c;inttksm(a,b/2,c);if(b%20)returnt*t%c;returnt*t%c*a%c;}signedmain(){for(inti2;i1e6;i){if(isp[i]){continue;}for(intji;j1e6;ji){isp[j]1;intxj;while(x%i0){mp[j][i];x/i;}}isp[i]0;}cinn;for(inti1;in;i){cina[i];for(mapint,int::iterator itmp[a[i]].begin();it!mp[a[i]].end();it){intxit-first,yit-second;if(y%2!0){cnt[x];}}}for(inti2;i1e6;i){if(isp[i]){continue;}if(cnt[i]!0cnt[i]n){ansans*ksm(i,min(cnt[i],n-cnt[i]),mod)%mod;}}coutansendl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容