T1
第一种做法，考虑\(a_0,a_1,b_0,b_1\)的因子间的关系。
对于任意一个因子，用\(k\)来表示该因子的数量。
一定有
- 当\(k_{a0}>k_{a1}\)时，\(k_x==k_{a1}\)，不然gcd一定不为\(a_1\)
- 当\(k_{a0}==k_{a1}\)时，只需要\(k_x>=k_{a1}\)
- 当\(k_{a0}<k_{a1}\)时，gcd一定取不到\(k_{a1}\)，此时无解
对于\(b\)的分析也是同理
- 当\(k_{b0}<k_{b1}\)时，\(k_x==k_{b1}\)，不然lcm一定不为\(b_1\)
- 当\(k_{b0}==k_{b1}\)时，只需要\(k_x<=k_{b1}\)
- 当\(k_{b0}>k_{b1}\)时，lcm一定取不到\(k_{b1}\)，此时无解
最后用分步乘法原理把它乘起来就行
这个解法个人感觉比较难写，但是我把它调出来了，我好棒？？
#include<cstdio>
const int N=44800;
bool nprime[N];
int prime[N];
void getp(int n){
for(int i=2;i<=n;i++){
if(!nprime[i])
prime[++prime[0]]=i;
for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++){
nprime[i*prime[j]]=1;
if(i%prime[j]==0)
break;
}
}
}
int a0,a1,b0,b1;
long long res;
int find(int &x,int &t){
int cnt=0;
while(x%t==0){
cnt++;
x/=t;
}
return cnt;
}
bool calc(int t){
if(t>b1)return 1;
if(b1%t!=0)return 0;
int cnt=1;
int ka1=find(a1,t);
int ka0=find(a0,t);
int kb0=find(b0,t);
int kb1=find(b1,t);
if(ka1<ka0&&kb0<kb1&&ka1==kb1)cnt=1;
else if(ka1<ka0&&kb0==kb1&&ka1<=kb1)cnt=1;
else if(ka1==ka0&&kb0<kb1&&ka1<=kb1)cnt=1;
else if(ka1==ka0&&kb0==kb1&&ka1<=kb1)cnt=kb1+1-ka1;
else cnt=0;
res*=cnt;
return 0;
}
int main(){
getp(N-2);
int T;
scanf("%d",&T);
while(T--){
res=1;
scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
for(int i=1;i<=prime[0];i++)
if(calc(prime[i]))break;
if(b1!=1)calc(b1);
printf("%lld\n",res);
}
}
第二种做法，考虑推导一下公式。
已知\(gcd(x,a_0)==a_1\)，\(lcm(x,b_0)==b_1\)
由gcd的式子，可以推出\(gcd(\frac{x}{a_1},\frac{a_0}{a_1})==1\)
注意lcm没有这个性质，但可以转化成gcd，即\(xb_0\over gcd(x,b_0)\)\(==b_1\)
进一步化简得到，\(xb_0==gcd(xb_1,b_0b_1)\)
然后得到\(gcd(\frac{b_1}{b_0},\frac{b_1}{x})\)
根据这两个式子，我们只需要枚举到\(\sqrt{b_1}\),然后判断是不是符合条件就行。
借一下\(DarthVictor\)大佬的代码，这个写法我没写
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
int main() {
int T;
cin>>T;
while(T--) {
int a0,a1,b0,b1;
cin>>a0>>a1>>b0>>b1;
int p=a0/a1,q=b1/b0,ans=0;
for(int x=1;x*x<=b1;x++)
if(b1%x==0){
if(x%a1==0&&gcd(x/a1,p)==1&&gcd(q,b1/x)==1) ans++;
int y=b1/x;
if(x==y) continue;
if(y%a1==0&&gcd(y/a1,p)==1&&gcd(q,b1/y)==1) ans++;
}
cout<<ans<<endl;
}
return 0;
}
T2
这是一个裸的欧拉筛。。。。。
#include<cstdio>
const int N=3e6+10;
int prime[N],phi[N];
bool nprime[N];
void init(int n){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!nprime[i]){
prime[++prime[0]]=i;
phi[i]=i-1;
}
for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++){
nprime[i*prime[j]]=1;
if(i%prime[j])
phi[i*prime[j]]=(prime[j]-1)*phi[i];
else {
phi[i*prime[j]]=prime[j]*phi[i];
break;
}
}
}
}
int main(){
init(N-5);
int a,b;
while(~scanf("%d%d",&a,&b)){
long long res=0;
for(int i=a;i<=b;i++)
res+=phi[i];
printf("%lld\n",res);
}
}
T3
不妨设\(gcd(x,N)==k\)，那么\(gcd(\frac{x}{k},\frac{N}{k})==1\)。
所以枚举到\(\sqrt{N}\)找到因子，统计答案即\(\phi(\frac{N}{k})\)
注意特判\(i×i==N\)的情况。
#include<cstdio>
int clac(int x){
int res=1;
for(int i=2;i*i<=x;i++){
if(x%i)continue;
x/=i;res*=i-1;
while(x%i==0){
x/=i;res*=i;
}
}
if(x>1)res*=x-1;
return res;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int res=0;
int N,M;
scanf("%d%d",&N,&M);
for(int i=1;i*i<=N;i++){
if(N%i)continue;
if(i>=M)res+=clac(N/i);
if(i*i!=N&&N/i>=M)res+=clac(i);
}
printf("%d\n",res);
}
}
T4
举几个例子发现，如果\(gcd(x,y)!=1\)，那么它一定会被前边的某个点遮住，所以要统计的即\(gcd(x,y)==1\)的情况。
答案即，\(\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}gcd(x,y)==1\)
考虑化简这个式子，我们可以把中间的那一斜列拿掉，即\(x==y\)的情况，这种只对答案贡献1，然后就分为了两个三角形，不难发现这两个三角形对应的答案一样，因为对于每个三角形中的\((a,b)\)，另一个三角形里边一定有一个\((b,a)\)
所以只考虑下边的三角形即可，发现答案化简为\(2×\sum_{x=1}^{n-1}\sum_{y=0}^{x-1}gcd(x,y)==1\)
即\(2×\sum_{i=1}^{n-1}\phi(i)+1\)
注意对于\(y=0\)的情况，因为这时我们求\(gcd(x,y)\)会直接返回\(x\)的值，而只有当\(x==1\)的时候\(gcd\)才为1，所以可以不用特判。
#include<cstdio>
const int N=4e4+10;
bool nprime[N];
int prime[N],phi[N];
void init(int n){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!nprime[i]){
prime[++prime[0]]=i;
phi[i]=i-1;
}
for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++){
nprime[i*prime[j]]=1;
if(i%prime[j])
phi[i*prime[j]]=phi[i]*(prime[j]-1);
else {
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
}
phi[i]+=phi[i-1];
}
}
int main(){
int n;
scanf("%d",&n);
init(n-1);
printf("%d\n",2*phi[n-1]+1);
}
T5
要求出\(\sum_{i=1}^Ngcd(i,N)\)，直接求出肯定会T掉。
考虑变形为，\(\sum{d|N}d×\sum_{i=1}^N(gcd(i,N)==d)\)，理解一下这个式子，最大公约数一定是\(N\)的约数，所以每有一个\(gcd==d\)就会对答案产生一个\(d\)的贡献。
然后\(\sum_{i=1}^N(gcd(i,N)==d)==\sum_{i=1}^N(gcd(\frac{i}{d},\frac{N}{d})==1)==\phi(\frac{N}{d})\)
仍旧是只枚举到\(\sqrt{N}\)。
#include<cstdio>
#define ll long long
ll euler(ll x){
ll res=1;
for(int i=2;i*i<=x;i++){
if(x%i)continue;
x/=i;res*=i-1;
while(x%i==0){
x/=i;res*=i;
}
}
if(x>1)res*=x-1;
return res;
}
int main(){
ll n,res=0;
scanf("%lld",&n);
for(int i=1;i*i<=n;i++){
if(n%i)continue;
res+=i*euler(n/i);
if(i*i!=n)res+=n/i*euler(i);
}
printf("%lld\n",res);
}
T6
因为阶乘乘出来十分大，所以需要边乘边取mod，我不认为有人愿意写高精度
因为\(M!|N!\)，与\(M!\)互质的数一共有\(\frac{N!}{M!}×\phi(M!)\)个，乘开化简后可以得到\(N!×\prod_i(\frac{p_i-1}{p_i})\)
所以只需要在跑欧拉筛的时候顺便维护一下逆元和阶乘即可。
看起来是对的，但是被PinkRabbit大佬hack了。。。。
正解目前也看的不是很懂，先咕了。
#include<cstdio>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i<(b);++i)
int T,Mod,n,m;
int primes[664580], pnum=0;
bool isn_prime[10000001];
int pi[664580],inv[10000001];
int in[664580],fct[10000001];
int pos[10000001];
void init(){
isn_prime[0]=isn_prime[1]=1;
F(i,2,10000000){
if(!isn_prime[i]) primes[++pnum]=i;
for(int j=1;j<=pnum&&primes[j]*i<=10000000;++j){
isn_prime[primes[j]*i]=1;
if(i%primes[j]==0) break;
}
}
inv[1]=1; for(int i=2;i<Mod&&i<=10000000;++i)
inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;
pi[0]=1; F(i,1,pnum) pi[i]=1ll*pi[i-1]*(primes[i]-1)%Mod;
in[0]=1; F(i,1,pnum) if(primes[i]!=Mod) in[i]=1ll*in[i-1]*inv[primes[i]%Mod]%Mod; else in[i]=in[i-1];
fct[0]=1; F(i,1,10000000) if(i!=Mod) fct[i]=1ll*fct[i-1]*i%Mod; else fct[i]=fct[i-1];
F(i,2,10000000) if(isn_prime[i]) pos[i]=pos[i-1]; else pos[i]=pos[i-1]+1;
}
int main(){
scanf("%d%d",&T,&Mod);
init();
while(T--){
scanf("%d%d",&n,&m);
if(n>=Mod&&m<Mod) puts("0");
else printf("%d\n",1ll*fct[n]*pi[pos[m]]%Mod*in[pos[m]]%Mod);
}
return 0;
}
T7
exgcd裸题，要求\(ax\equiv1\pmod{b}\)
可以把它变化成为\(ax-by=1\)，
因为只求\(x\)，所以变换\(y\)的系数没关系，得到\(ax+by==1\)
因为一定有解，所以，\(gcd(a,b)==1\)，所以\(bx'+a%by'==1\)
然后得到\(ax+by==bx'+(a-\lfloor\frac{a}{b}\rfloor)y'\)
又因为求整数解，所以让对应的系数相等即可。
得到\(x=(a-\lfloor\frac{a}{b}\rfloor)y'\),\(y=x'\)
#include<cstdio>
#define ll long long
void exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1;
y=0;
return ;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
int main(){
ll a,b,x,y;
scanf("%lld%lld",&a,&b);
exgcd(a,b,x,y);
printf("%lld\n",(x%b+b)%b);
}
T8
还是个exgcd。
假设跳了\(k\)次后相遇，那么\(x+km\equiv y+nk\pmod{L}\)
化简可以得到\(k(n-m)+pL==x-y\)，其中p为常数。
然后只要解出\(k\)即可。
但这里让求最小整数解，所以考虑转化。
令特解为\(x_0,y_0\)，那么有
\(ax_0+by_0==ax+by\)
\(a(x_0-x)==b(y-y_0)\)
\(\frac{a}{gcd(a,b)}(x_0-x)==\frac{b}{gcd(a,b)}(y-y_0)\)
这时由于系数是互质的，
\(x_0-x==\frac{b}{gcd(a,b)}\),
所以\(x==x_0-\frac{b}{gcd(a,b)}\)。
#include<cstdio>
#define ll long long
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1;
y=0;
return a;
}
ll g=exgcd(b,a%b,y,x);
y-=a/b*x;
return g;
}
int main(){
ll x,y,n,m,L;
scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L);
ll a=n-m,c=x-y,b=L;
if(a<0)a=-a,c=-c;
ll g=exgcd(a,b,x,y);
if(m==n||c%g)
printf("Impossible\n");
else
printf("%lld\n",(c/g*x%(b/g)+b/g)%(b/g));
}
T9
思路基本和上一个差不多，主要考虑什么时候得到体积最小
\(V==-ax+by\)，如果它要是有解，那么\(gcd(a,b)|V\)，所以\(V_min==gcd(a,b)\)
#include<cstdio>
#define lqs long long
lqs exgcd(lqs a,lqs b,lqs &x,lqs &y){
if(b==0){
x=1;
y=0;
return a;
}
lqs g=exgcd(b,a%b,y,x);
y-=a/b*x;
return g;
}
int main(){
lqs a,b,x,y;
scanf("%lld%lld",&a,&b);
lqs g=exgcd(a,b,x,y);
printf("%lld\n",g);
x*=-1;a*=-1;
while(x<0||y<0){
x+=(x<0)?b/g:0;
y-=(x>=0)?a/g:0;
}
printf("%lld %lld\n",x,y);
}
T10
显然是递推求逆元。
设\(Mod=ki+r\)，则有\(ki+r\equiv 0\pmod{Mod}\)
同时乘上\(i^{-1}r^{-1}\)得到\(kr^{-1}+i_{-1}\equiv 0\pmod{Mod}\)
所以\(i^{-1}\equiv-kr^{-1}\pmod{Mod}\)
即\(i^{-1}\equiv-\lfloor\frac{Mod}{i}\rfloor(p%i)^{-1}\)
T11
一种是去找循环节，但是时间复杂度显然很SPFA。
易得当\(x<=\frac{n}{2}\)时，\(x=2x\)。
当\(x>\frac{n}{2}\)时，\(x=2x-n-1\)
那么有没有什么好的办法来用一个统一的式子表示呢？
显然\(2x\equiv 2x-n-1 \pmod{n+1}\)
所以只要%上一个\(n+1\)即可，最后得到的答案也不会受到影响因为起始位置一定小于\(n+1\)
所以解方程\(2^Mx==L\pmod{n+1}\)即可。
解得方法有很多，随便挑一种就行。
还有洛谷上的数据经过魔改所以过不掉
#include<iostream>
using namespace std;
typedef long long ll;
ll pow(ll a,ll b,ll c){
ll ans=1;
while(b){
if(b&1)ans=ans*a%c;
a=a*a%c;
b>>=1;
}
return ans;
}
void exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1;
y=0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
int main(){
ll n,m,l,x,y;
cin>>n>>m>>l;
exgcd(pow(2,m,n+1),n+1,x,y);
cout<<(l*x%(n+1)+n+1)%(n+1);
}
尾声
赶来赶去最后终于是在十一点之前搞完了，正如题目说的那样，数论基础，数学的学习才刚刚开始，后边还有更大的挑战。
由于写的匆忙，所以有些地方可能会写错，只是笔误，欢迎指正。
代码可以复制粘贴但有些题目代码加有防伪标记，咳咳咳咳