【T】03

板子，略

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,p,k;
int main()
{scanf("%lld%lld%lld",&a,&p,&k);printf("%lld^%lld mod %lld=",a,p,k);ll ans=1,w=a;a%=k;while(p){if(p&1){ans=ans*w%k;}w=w*w%k;p>>=1;}printf("%lld",ans%k);
}

B【模板】矩阵快速幂

#include<bits/stdc++.h>
using namespace std;
long long mod=1000000007;
long long n,k;
struct sq{long long num[102][102];sq(){memset(num,0,sizeof(num));}//初始化num数组为空
};
sq operator *(const sq &a,const sq &b)
{sq ans;for(int k=1;k<=n;k++)for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){ans.num[i][j]=(ans.num[i][j]+a.num[i][k]*b.num[k][j]%mod)%mod;}}return ans;
}//一个重载
sq x,y,ans;
long long read()
{char s;long long ans=0;s=getchar();while(s>'9'||s<'0'){s=getchar();}while(s>='0'&&s<='9'){ans=ans*10+s-'0';s=getchar();}return ans;
}//只是个快速读入函数
inline void init()
{n=read();k=read();//用scanf,cin也行for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)x.num[i][j]=read();for(int i=1;i<=n;i++){y.num[i][i]=1;ans.num[i][i]=1;}
}
int main(){init();while(k){if(k&1){ans=ans*x;}x=x*x;k>>=1;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%lld ",ans.num[i][j]);printf("\n");}return 0;
}

C【模板】有理数取余
除以一个数等于乘以它的逆元，逆元可以用费马小定理求

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll a,b,mod=19260817;
inline ll read()
{ll ans=0;char s=getchar();while(s>'9'||s<'0')s=getchar();while(s>='0'&&s<='9'){ans=((ans<<1)%mod+(ans<<3)%mod+(s&15))%mod;s=getchar();}return ans;
}
ll quick_m(ll i,ll n)
{i%=mod;ll ans=1,ds=i;while(n){if(n&1){ans=ans*ds%mod;}ds=ds*ds%mod;n>>=1;}return ans%mod;
}
signed main(){a=read();b=read();if(b==0){printf("Angry!");return 0;}printf("%lld",a*quick_m(b,mod-2)%mod);return 0;
}

D 质因数分解

#include<bits/stdc++.h>
int a;
int main()
{scanf("%d",&a);for(int i=2;i*i<=a;i++){if(a%i==0){printf("%d",std::max(a/i,i));return 0;//找到一个因数就可以停了，另一个因数就是最大的那个}}
}

E 质数筛
数据不大的话，每个数都直接用质数判断法也能过

#include<bits/stdc++.h>
using namespace std;
int n,a;
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a);bool f=1;for(int j=2;j*j<=a;j++){if(a%j==0){f=0;break;}}if(f==1&&a!=1)printf("%d ",a);//是质数}
}

F 【模板】线性筛素数
这里用的欧拉筛

#include<bits/stdc++.h>
using namespace std;
bool ans[100000002];
int z[6000005],p;
int n,m,a;
int main()
{scanf("%d%d",&n,&m);for(int i=2;i<=n;i++){if(!ans[i])z[++p]=i;//printf("[%d]",z[p]);for(int j=1;j<=p&&z[j]*i<=n;j++){ans[i*z[j]]=1;if(i%z[j]==0)break;}}for(int i=1;i<=m;i++){scanf("%d",&a);printf("%d\n",z[a]);}return 0;
} 

G 晨跑
求三个数的最小公倍数

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll gcd(ll x,ll y){return !y?x:gcd(y,x%y);}
ll lcm(ll x,ll y){return x*y/gcd(x,y);}
int main()
{ll a,b,c;scanf("%lld%lld%lld",&a,&b,&c);printf("%lld",lcm(a,lcm(b,c)));
}

H 最大公约数和最小公倍数问题
$x\ast y=gcd(x,y)\ast lcm(x,y)$
枚举x然后判断算出对应y是否满足gcd,lcm就行，可能要特判

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll gcd(ll x,ll y){return !y?x:gcd(y,x%y);}
ll lcm(ll x,ll y){return x*y/gcd(x,y);}
int main()
{ll a,b,ans=0;scanf("%lld%lld",&a,&b);if(a==b)ans--;//这样会存在x,y相同的一组，下面枚举时会多算一组，故删去for(ll i=1;i*i<=a*b;i++)if(a*b%i==0&&gcd(i,a*b/i)==a)ans+=2;printf("%lld",ans);
}

I 【模板】模意义下的乘法逆元
建议看我之前博客线性递推式部分
$a^{-1}=-\lfloor p/a\rfloor \ast (pmoda{)}^{-1}(modp)$

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int n,p,inv[3000005];
signed main(){scanf("%d%d",&n,&p);inv[0]=1;inv[1]=1;printf("1\n");for(int i=2;i<=n;i++){inv[i]=(ll)inv[p%i]*(p-p/i)%p;//-p/i不能直接取模，要+p变成正数再%pprintf("%d\n",inv[i]);}return 0;
}
/*下面是欧拉筛版
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3000005;
ll n,p;
bool vis[N];
ll z[N];
ll inv[N];
ll quick(ll a,ll k,ll mod)
{ll ans=1,as=a;while(k){if(k&1){ans=ans*as%mod;}as=as*as%mod;k>>=1;}return ans;
}
int main()
{scanf("%lld%lld",&n,&p);vis[1]=1,inv[1]=1;for (int i=2;i<=n;i++){//printf("(%d\n",i);if (!vis[i])z[++z[0]]=i,inv[i]=quick(i,p-2,p);for (int j=1;j<=z[0]&&i*z[j]<=n;j++){vis[i*z[j]]=1;inv[i*z[j]]=(inv[i]*inv[z[j]])%p;if (i%z[j]==0) break;}}for (int i=1;i<=n;i++)printf("%lld\n",inv[i]);return 0;
}*/

J 沙拉公主的困惑
求$1->N!$中与$M!$互质的个数

推演一下，最后得$\frac{N!}{M!}\varphi (M!)$
=>$N!(\frac{1-p_1}{p_1})(\frac{1-p_2}{p_2})...(\frac{1-p_k}{p_k})$
一堆预处理，质数+线性求逆+阶乘。。。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
inline ll read()
{ll ans=0;char s=getchar();while(!isdigit(s))s=getchar();while(isdigit(s)){ans=(ans*10)+(s&15);s=getchar();}return ans;
}
const int N=1e7+10;
int T;
ll n,m,mod;
int z[N],p;
bool vis[N];
void get_prime()
{for(int i=2;i<N;i++){if(!vis[i])z[++p]=i;for(int j=1;j<=p&&i*z[j]<N;j++){vis[i*z[j]]=1;if(i%z[j]==0)break;}}
}
ll inv[N],mul[N],pt[N];
int main()
{scanf("%d%lld",&T,&mod);get_prime();inv[1]=1;inv[0]=1;for(int i=2;i<N;i++)inv[i]=inv[mod%i]*(mod-mod/i)%mod;mul[1]=1;for(int i=2;i<N;i++)mul[i]=mul[i-1]*i%mod;pt[1]=1;for(int i=2;i<N;i++)if(!vis[i])pt[i]=pt[i-1]*(i-1)%mod*inv[i%mod]%mod;else pt[i]=pt[i-1];while(T--){n=read();m=read();printf("%lld\n",mul[n]*pt[m]%mod);}
}//开个o2就过了

K 同余方程
扩欧板子题

#include<bits/stdc++.h>
using namespace std;
void gcd(int a,int b,int &x,int &y)
{if(!b){x=1;y=0;return ;}gcd(b,a%b,x,y);int xx=y,yy=x-a/b*y;x=xx;y=yy;return ;
}
int a,b,x,y;
int main()
{scanf("%d%d",&a,&b);gcd(a,b,x,y);printf("%d",(x+b)%b);
}