题解好像还没有C++矩阵题解吧

cangjunyuehan @ 2024-10-16 13:39:16

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e7+10,mod=9901;
ll m,n,num[N],sum=1;
bool su[N];
queue<ll> q;
struct matrix{
    ll m[2][2];
};
matrix operator * (const matrix &a,const matrix &b){
    matrix c;
    memset(c.m,0,sizeof(c.m));
    for(int i=0;i<2;++i)
    for(int j=0;j<2;++j)
    for(int k=0;k<2;++k)
    c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
    return c;
}
ll ksm(ll s,ll t){
    matrix ans,a;
    a.m[0][0]=s,a.m[1][0]=s,a.m[1][1]=1,a.m[0][1]=0;
    ans.m[0][0]=1,ans.m[0][1]=0,ans.m[1][1]=1,ans.m[1][0]=0;
    while(t>0){
        if(t&1) ans=ans*a;
        a=a*a;
        t>>=1;
    }
    return ans.m[1][0];
}
void _init(){
    su[1]=true;
    for(int i=2;i<=sqrt(m);++i)
    if(!su[i])
    for(int j=2;j<=sqrt(m);++j)
        su[i*j]=true;
    ll i=1;
    while(m^1){
        while(su[i]) ++i;
        if(!(m%i)){
            if(!num[i]) q.push(i);
            ++num[i];
            m/=i;
        }
        else ++i;
    }
}
int main(){
    matrix b;
    scanf("%ld%ld",&m,&n);
    _init();
    while(!q.empty()){
        ll i=q.front();
        q.pop();
        sum*=(ksm(i,n*num[i])+1);
        sum%=mod;
    }
    printf("%ld",sum);
    return 0;
}

by lostxxx @ 2024-10-16 13:58:59

你可以写好一篇题解然后 at 管理员申请加入题解。

by cangjunyuehan @ 2024-10-16 16:19:07

@lostxxx 我是蒻蒻（我也不知道是哪个字），让其他大佬来吧。

by cangjunyuehan @ 2024-10-16 16:21:02

@cangjunyuehan 之前那个判断质因数太慢了，又写了个快的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e7+10,mod=9901;
ll m,n,num[N],pre[N],sum=1,cnt;
bool su[N];
queue<ll> q;
struct matrix{
    ll m[2][2];
};
matrix operator * (const matrix &a,const matrix &b){
    matrix c;
    memset(c.m,0,sizeof(c.m));
    for(int i=0;i<2;++i)
    for(int j=0;j<2;++j)
    for(int k=0;k<2;++k)
    c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
    return c;
}
ll ksm(ll s,ll t){
    matrix ans,a;
    a.m[0][0]=s,a.m[1][0]=s,a.m[1][1]=1,a.m[0][1]=0;
    ans.m[0][0]=1,ans.m[0][1]=0,ans.m[1][1]=1,ans.m[1][0]=0;
    while(t>0){
        if(t&1) ans=ans*a;
        a=a*a;
        t>>=1;
    }
    return ans.m[1][0];
}
void _init(){
    su[1]=true;
    pre[0]=1;
    for(int i=2;i<=m/pre[cnt];++i){
        if(!su[i]){
            pre[++cnt]=i;
            if(!(m%i)){
                q.push(i);
                while(!(m%i)){
                    m/=i;
                    ++num[i];
                }
            }
        }
        for(int j=1;j<=cnt;++j){
            if(i*pre[j]>m) break;
            su[i*pre[j]]=true;
            if(!(i%pre[j])) break;
        }
    }
    if(m^1){
        q.push(m);
        ++num[m];
    }
}
int main(){
    matrix b;
    scanf("%ld%ld",&m,&n);
    _init();
    while(!q.empty()){
        ll i=q.front();
        q.pop();
        sum*=(ksm(i,n*num[i])+1);
        sum%=mod;
    }
    printf("%ld",sum);
    return 0;
}