P5435 基于值域预处理的快速 GCD

P5435 基于值域预处理的快速 GCD

思路

也就是将x分解成a * b * c,然后在分别与另一个数求解gcd
0-1000之内的gcd是可以直接预处理出来的，因为gcd(a,b) = gcd(a%b,b)（a>b)

为什么不分解成两个数呢，因为需要保证>1000的那个数一定是质数

代码

//基于值域的预处理
//也就是大事化小，小的又可以直接算
//将一个1e6的数华为几个小的数，然后直接进行处理就可以了
#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
using ll=long long;
const int N=5005,M=1e6+5;

vector<int>prime;
bitset<M>st;
int k[M][3],GCD[1005][1005];

void init(int n=1000,int m=1000000) {
    st[1]=1;
    k[1][0]=k[1][1]=k[1][2]=1;
    for(int i=2;i<=m;i++) {
        if(st[i]==0)prime.push_back(i),k[i][0]=1,k[i][1]=i;
        for(auto x:prime) {
            int y=x*i;
            if(y>m)break;
            st[y]=1;
            k[y][0]=k[i][0]*x;
            k[y][1]=k[i][1];
            if(k[y][0]>k[y][1])swap(k[y][0],k[y][1]);
            if(i%x==0)break;
        }
    }
    for(int i=1;i<=n;i++)GCD[i][0]=GCD[0][i]=i;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            GCD[i][j]=GCD[j][i]=GCD[i%j][j];
}

int gcd(int a,int b) {
    int ans=1,tmp;
    for(int i=0;i<=1;i++) {
        if(k[a][i]>1000) {
            if(b%k[a][i]==0)tmp=k[a][i];
            else tmp=1;
        }
        else tmp=GCD[k[a][i]][b%k[a][i]];
        b/=tmp;
        ans*=tmp;
    }
    return ans;
}

int a[N],b[N];

signed main() {
    init();
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++) {
        ll now=1,ans=0;
        for(int j=1;j<=n;j++) {
            now=now*i%mod;
            ans=(ans+now*gcd(a[i],b[j]))%mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}