[Gym 102114C]Call It What You Want

Link

给的\Phi_d的复数形式的公式是骗人玩的…很好我又被骗了…

Solution

x^n-1=\prod_{d|n}\Phi_d(x)\Leftrightarrow \Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(\frac nd)}
\Phi_d(x)的最高次项为\varphi(d),所以在模x^{\varphi(d)+1}下求出\Phi_n(x)然后再求答案,单次询问的复杂度为\mathcal{O}(\sum_{d | n}{2^{\omega(d)}\varphi(d)}) = \mathcal{O}(2^6 n)

Code

#include <bits/stdc++.h>

const int N=1e5,XN=N+11;

int prime[XN],pcnt,phi[XN];
std::vector<int> pdv[XN];

void Prep() {
    static bool notPrime[XN];
    phi[1]=1;
    for(int i=2;i<=N;++i) {
        if(!notPrime[i]) {
            prime[++pcnt]=i;
            phi[i]=i-1;
            pdv[i]={i};
        }
        for(int j=1;j<=pcnt && i*prime[j]<=N;++j) {
            notPrime[i*prime[j]]=1;
            pdv[i*prime[j]]=pdv[i];
            if(i%prime[j]==0) {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            } else {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
                pdv[i*prime[j]].push_back(prime[j]);
            }
        }
    }
}

//P只有复根 无法因式分解

std::vector<int> FindDivisors(int x) {
    std::vector<int> res={};
    for(int d=1;d*d<=x;++d)
        if(x%d==0) {
            res.push_back(d);
            if(x!=d*d)
                res.push_back(x/d);
        }
    return res;
}

std::vector<int> Calc(int n) {
    std::vector<int> posi,nega;
    for(int S=0;S<(1<<pdv[n].size());++S) {
        int d=1;
        for(size_t i=0;i<pdv[n].size();++i)
            if(S>>i&1)
                d*=pdv[n][i];
        (__builtin_popcount(S)&1?nega:posi).push_back(n/d);
    }
    std::vector<int> P{1};
    for(auto d : posi) {
        //P*=(x^d-1)
        std::vector<int> T(P.size()+d,0);
        for(size_t i=0;i<P.size();++i) {
            T[i]-=P[i];
            T[i+d]+=P[i];
        }
        P=T;
    }
    for(auto d : nega) {
        //P/=(x^d-1)
        std::vector<int> T(P.size()-d,0);
        for(int i=T.size()-1;i>=0;--i) {
            T[i]=P[i+d];
            P[i]+=P[i+d];
            P[i+d]=0;
        }
        P=T;
    }
    return P;
}

void Work() {
    int n;std::cin>>n;
    auto divisor=FindDivisors(n);
    std::vector<std::vector<int>> Ans;
    for(int d : divisor)
        Ans.push_back(Calc(d));
    std::sort(Ans.begin(),Ans.end(),[](auto const &a,auto const &b)->bool {
        if(a.size()!=b.size())
            return a.size()<b.size();
        else
            for(int i=a.size()-1;i>=0;--i)
                if(a[i]!=b[i])
                    return a[i]<b[i];
            assert(0);
    });
    for(auto &v : Ans) {
        std::cout<<'(';
        for(int i=v.size()-1;i>=0;--i)
            if(v[i]) {
                if(v[i]>0 && i!=(int)v.size()-1)
                    std::cout<<'+';
                else if(v[i]<0)
                    std::cout<<'-';
                if(abs(v[i])!=1 || i==0)
                    std::cout<<abs(v[i]);
                if(i) {
                    std::cout<<'x';
                    if(i>=2)
                        std::cout<<'^'<<i;
                }
            }
        std::cout<<')';
    }
    std::cout<<'\n';
}

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    Prep();
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注