打卡信奥刷题（3473）用C++实现信奥题 P10580 [蓝桥杯 2024 国 A] gcd 与 lcm

P10580 [蓝桥杯 2024 国 A] gcd 与 lcm题目描述给定两个数x,yx,yx,y求有多少种不同的长度为nnn的序列(a1,a2,⋯ ,an)(a_1,a_2,\cdots,a_n)(a1​,a2​,⋯,an​)其所有元素的最大公约数为xxx且最小公倍数为yyy。两个序列(a1,a2,⋯ ,an)(a_1,a_2,\cdots,a_n)(a1​,a2​,⋯,an​)与(b1,b2,⋯ ,bn)(b_1,b_2,\cdots,b_n)(b1​,b2​,⋯,bn​)不同是指存在至少一个位置iii满足ai≠bia_i\neq b_iai​bi​。由于答案可能很大请输出答案对998 244 353998\ 244\ 353998244353取模后的结果。输入格式输入的第一行包含一个整数QQQ表示询问次数。接下来QQQ行每行包含三个整数x,y,nx,y,nx,y,n表示一组询问相邻整数之间使用一个空格分隔。对于每个询问保证至少存在一个满足条件的序列。输出格式输出QQQ行每行包含一个整数依次表示每个询问的答案。输入输出样例 #1输入 #13 3 6 2 12 144 3 233 251640 10输出 #12 72 905954656说明/提示对于40%40\%40%的评测用例n≤30n\le 30n≤30对于70%70\%70%的评测用例n≤5000n\le 5000n≤5000对于所有评测用例1≤Q≤1001\le Q\le 1001≤Q≤1002≤n≤1052\le n\le 10^52≤n≤1051≤x,y≤1091\le x,y\le 10^91≤x,y≤109。C实现#includecstdio#includecstringusingnamespacestd;constintN35,MOD998244353;intq,cnt,p[N],k[N];voidgetprime(intx){//分解质因数cnt0;for(inti2;i*ix;i){if(x%i0){k[cnt]0;//提前清空while(x%i0){x/i;k[cnt];}}}if(x!1)k[cnt]1;//注意如果没分解完说明剩下的是单独的一个质数}longlongqpow(longlongx,longlongy){longlongret1;while(y){if(y1)retret*x%MOD;y1;xx*x%MOD;}returnret;}intmain(){scanf(%d,q);while(q--){intx,y,n;longlongans1;scanf(%d%d%d,x,y,n);getprime(y/x);for(inti1;icnt;i){longlongtmpqpow(k[i]1,n);tmp(tmp-qpow(k[i],n))%MOD;tmp(tmp-qpow(k[i],n))%MOD;tmp(tmpqpow(k[i]-1,n))%MOD;tmp(tmpMOD)%MOD;ansans*tmp%MOD;}printf(%lld\n,(ansMOD)%MOD);//注意再加一次模数防止出负}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容