wordpress做招聘网站,太原市做网站,公司网站域名注册费用,海晏网站制作当时在做洛谷U389682 最大公约数合并的时候我就想到把每个质因子分解出来然后跑高维前缀和#xff0c;但是那一道题不是用这个方法#xff0c;所有我也一直在思考这种做法是不是真的有用。因为昨天通过2024上海大学生程序设计竞赛I-六元组计数这道题我了解到了不少关于原根的…
当时在做洛谷U389682 最大公约数合并的时候我就想到把每个质因子分解出来然后跑高维前缀和但是那一道题不是用这个方法所有我也一直在思考这种做法是不是真的有用。因为昨天通过2024上海大学生程序设计竞赛I-六元组计数这道题我了解到了不少关于原根的性质所以想着回来做去年网络赛的题目。因为我当时完全不了解原根因此做不了这个题目更看不懂题解但是我现在已经大概掌握原根的知识所以感觉做这道题还算比较轻松而且这道题里面刚好就用到了曾经想到的质因数分解高维前缀和感觉十分有趣于是写博客记录。
因为原根的题目一般都喜欢把0先处理掉然后在处理不为0的情况。 很显然如果想让左右两边为0只需要满足 n ∣ x , n ∣ y n|x,n|y n∣x,n∣y方案数为 ( n − 1 ) 2 (n-1)^2 (n−1)2。
然后我的想法是先列出一个 ( n − 1 ) ∗ ( n − 1 ) (n-1)*(n-1) (n−1)∗(n−1)的表 1 x n − 1 , 1 y n − 1 , a i , j i j 1xn-1,1yn-1,a_{i,j}i^j 1xn−1,1yn−1,ai,jij。实际上表上每一个位置都表示 n ∗ ( n − 1 ) n*(n-1) n∗(n−1)个数因为实际上它的行坐标可以加上若干个 n n n列坐标可以加上若干个 n − 1 n-1 n−1。然后就可以发现任意两个值相同的位置可以一样都恰好对应了一个解我也不清楚如果以前没有看过题解能不能想到这一步。比如两个坐标分别为 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1),(x_2,y_2) (x1,y1),(x2,y2)如果我们想形成一个解那么就必须要让 x 1 k 1 n y 2 k 2 ( n − 1 ) , y 1 k 3 ( n − 1 ) x 2 k 4 n x_1k_1ny_2k_2(n-1),y_1k_3(n-1)x_2k_4n x1k1ny2k2(n−1),y1k3(n−1)x2k4n这个根据扩展欧几里得可以知道如果想找到另外一个解那么 k 1 , k 4 k_1,k_4 k1,k4都必须改变 n − 1 n-1 n−1 k 2 , k 3 k_2,k_3 k2,k3都必须改变 n n n因此两个相同值的位置恰好对应一个解。
因此我们就必须算出每个数出现的次数答案就是这个出现次数的平方和。
根据原根的性质和 n − 1 n-1 n−1最大公因数相同的数出现次数一样 然后我们就把和 n − 1 n-1 n−1最大公因数相同的数全部在一个组然后考虑组合组之间的影响详见2024上海大学生程序设计竞赛I-六元组计数原根知识详解。
我们就考虑每个集合的最小的数那么只有它的因子所在的集合会出现这个数实际上就是一个周期出现一次, g c d ( x , n − 1 ) y gcd(x,n-1)y gcd(x,n−1)y的数有 y y y个周期所以贡献就是。 ( n − 1 ) 2 ∑ i ∣ n − 1 ϕ ( n − 1 i ) ( ∑ j ∣ i ϕ ( n − 1 j ) j ) 2 (n-1)^2\sum_{i|n-1}\phi(\frac{n-1}{i})(\sum_{j|i}\phi(\frac{n-1}{j})j)^2 (n−1)2∑i∣n−1ϕ(in−1)(∑j∣iϕ(jn−1)j)2
我们可以预处理出 2 ∗ 1 0 7 2*10^7 2∗107以内的质数实测表明n-1的所有素因子都不会超过4*10^14所有我只用处理出这么多然后分解完质因数就用高位前缀和把 ∑ j ∣ i ϕ ( n − 1 j ) j \sum_{j|i}\phi(\frac{n-1}{j})j ∑j∣iϕ(jn−1)j计算出来即可。
#includebits/stdc.h
#define rep(i,x,y) for(int ix;iy;i)
#define dwn(i,x,y) for(int ix;iy;i--)
#define ll long long
using namespace std;
templatetypename Tinline void qr(T x){x0;int f0;char sgetchar();while(!isdigit(s))f|s-,sgetchar();while(isdigit(s))xx*10s-48,sgetchar();xf?-x:x;
}
int cc0,buf[31];
templatetypename Tinline void qw(T x){if(x0)putchar(-),x-x;do{buf[cc]int(x%10);x/10;}while(x);while(cc)putchar(buf[cc--]0);
}
const int N2e710,M2e510,mod998244353;
int cnt;ll p[N];bool v[N];
ll n,ans;
struct node{ll x,y;
}a[210];int m;ll val[210];
ll phi[M],lim,dp[M],num[M];
void solve(){qr(n);if(n2){puts(2);return;}n--;ll nnn;ans(n%mod)*(n%mod)%mod;m0;rep(i,1,cnt){if(p[i]*p[i]n)break;if(n%p[i]0){a[m].xp[i];a[m].y0;while(n%p[i]0)a[m].y,n/p[i];}}if(n1)a[m](node){n,1};val[1]1;rep(i,2,m)val[i]val[i-1]*(a[i-1].y1);limval[m]*(a[m].y1);rep(i,0,lim-1){if(!i){phi[i]1;num[i]1;continue;}bool bk0;rep(j,1,m){ll ti/val[j]%(a[j].y1);if(t){if(t1)phi[i]phi[i-val[j]]*(a[j].x-1);else phi[i]phi[i-val[j]]*a[j].x;num[i]num[i-val[j]]*a[j].x;break;}}}rep(i,0,lim-1)dp[i](phi[lim-1-i]%mod)*(num[i]%mod)%mod;rep(i,1,m)rep(j,val[i],lim-1)if(j/val[i]%(a[i].y1))(dp[j]dp[j-val[i]])%mod;rep(i,0,lim-1){dp[i]dp[i]*dp[i]%mod;(ans(phi[lim-1-i]%mod)*dp[i]%mod)%mod;}coutansendl;
}
int main(){rep(i,2,20000000){if(!v[i])v[i]1,p[cnt]i;for(int j1;jcnti*p[j]20000000ll;j){v[i*p[j]]1;if(i%p[j]0)break;}}int tt;qr(tt);while(tt--)solve();return 0;
}
