A - A^B Mod C

给出3个正整数A B C，求A^B Mod C。
A,B,C范围都是0-1e9，所以要用快速幂，这题就是快速幂板子题。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+100;
ll pw(ll a,ll b,ll c)
{
	ll ans=1;
	while(b)
	{
		if(b%2) ans=(ans*a)%c;
		a=(a*a)%c;
		b/=2;
	} 
	return ans;
} 
int main()
{
	ll n,m,c;
	cin>>n>>m>>c;
	printf("%lld\n",pw(n,m,c));
	return 0;
} 

B - 逆元

阿克克希是求婚总动员的队长，他通过自己的双手，成就了无数年轻人的梦，但他却留下了悲伤的泪水。
求婚是非常费力的，他手上有 P-1个求婚请求，这 i 个人的编号为 [1,P-1]
面对第 i 个人他的求婚麻烦值为：i 在模 P 意义下的逆元。
他现在想知道总的麻烦值。
tips:如果有任意一个编号 i 在模 P 意义下不存在逆元，请输出 AKCniubi。
只有P为素数情况下才存在逆元，暴力算发现超时,打表可以发现[1,p-1]模P的逆元和就是1+2+…+p-1，可以直接用等差数列求和公式。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+100;
ll pw(ll a,ll b,ll c)
{
	ll ans=1;
	while(b)
	{
		if(b%2) ans=(ans*a)%c;
		a=(a*a)%c;
		b/=2;
	} 
	return ans;
} 
int prime(ll n)
{
	if(n<=1) return 0;
	for(ll i=2;i<=sqrt(n);i++){
		if(n%2==0) return 0;
	}
	return 1;
}
int main()
{
	ll n,m,p;
	cin>>p;
	if(!prime(p)) printf("AKCniubi\n");
	else 
	{
		printf("%lld\n",(p-1)*p/2);//等差数列通项公式；
	}
	return 0;
}

C - 判决素数个数

输入两个整数X和Y，输出两者->>之间<<-的素数个数（包括X和Y）。
X,Y范围都很小，判断素数就行，不过这个题有个坑就是X可能大于Y。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+100;
int x,y;
int prime(int n)
{
	if(n<=1) return 0;
	for(int i=2;i<=sqrt(n);i++){
		if(n%i==0) return 0;
	}
	return 1;
}
int main()
{
	cin>>x>>y;
	int t;
	if(x>y){
		t=x;
		x=y;
		y=t;
	}
	int ans=0;
	for(int i=x;i<=y;i++){
		if(prime(i)){
			ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

D - 矩阵乘法

直接循环遍历计算就可以。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+100;
int a[110][110],b[110][110],c[110][110];
int n,m,k;
int main()
{
	int n,m,k;
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	for(int i=1;i<=m;i++)
		for(int j=1;j<=k;j++)
			cin>>b[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=k;j++)
		{
			int sum=0;
			for(int z=1;z<=m;z++)
			{
				sum+=a[i][z]*b[z][j];
			}
			c[i][j]=sum;
		}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			printf("%d ",c[i][j]);
		}
		printf("\n");
	}
	return 0;
} 

E - Bash游戏

博弈问题，经典的巴什博弈。
常见的博弈问题可以参考这个链接博弈论

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+100;
int t,a,b;
int main()
{
	cin>>t;
	while(t--)
	{
		scanf("%d %d",&a,&b);
		if(a%(b+1)==0) printf("B\n");
		else printf("A\n"); 
	}
	return 0;
}

F - 取石子游戏

这道题是威佐夫博弈。具体了解威佐夫博弈可以参考上道题给的链接。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+100;
int a,b;
int main()
{
	while(~scanf("%d %d",&a,&b))
	{
		double r=(sqrt(5)+1)/2;
		int d=abs(a-b)*r;
		if(d!=min(a,b)) printf("1\n");
		else printf("0\n");
	}
	return 0;
} 

G - Matches Game

这道题是尼姆博弈。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+100;
int a[maxn];
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		int ans=0;
		for(int i=1;i<=n;i++){
			ans^=a[i];
		}
		if(ans) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

H - 互质数的个数（一）

这道题就是欧拉函数的计算，利用欧拉函数求互质数的个数，主要数据大小要开long long。欧拉函数具体了解参考这篇博客欧拉函数·

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+100;
int prime[maxn],euler[maxn],cnt;
bool judge[maxn];
ll get_eular(ll n)
{
	ll ans = n;
	for(ll i = 2;i<=n/i;i++){
		if(n%i == 0){
			while(n%i==0)
				n/=i;
			ans = ans/i*(i-1);
		}
	}
	if(n>1)
		ans = ans/n*(n-1);
	return ans;
}
int main()
{
	ll t,x;
	cin>>t;
	while(t--)
	{
		cin>>x;
		printf("%lld\n",get_eular(x));
	} 
	return 0;
}

I - Sumdiv

这道题用的数学知识有点多。
1，唯一分解定理:
A=(p1^n1p2n2p3n3…pknk); 把底数A分解 其中pi为素数
2，约数和定理：就是把A所有的约数
由上面我们，我们可以得出A=(p1n1p2n2p3n3…pknk)；
sum=(1+p11+p12+……p1n1) * (1+p21+p22+……p2n2) * ……(1+pk1+pk2……+pknk);
3,同余模公式:
(a+b)%m=(a%m+b%m);
(ab)%m=(a%mb%m);
题解：
先分解a的质因子，a=p1^t1p2t2*…pk^{tk(pi为质数)。再a}b=p1^(t1*b)*p2(t2b)…pk (tkb)。选出所有的因子就是枚举所有的tib，求和可知sum=(1+p1+…p1^{(t1*b))*(1+p2+…p2}(t2b))…(1+pk+…+pk*(tk*b));
再用等比数列公式求解约数和，求解过程因为数据太大要用到乘法逆元。
注意一种情况就是分母是mod的倍数时要特判。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=9901;
ll pow_mod(ll a,ll b,ll n)
{
    a=a%n;
    ll s=1;
    while(b){
        if(b&1)
        {
            s=(s*a)%n;
        }
    	a=(a*a)%n;
        b=b>>1;
    }
    return s;
}
int main()
{
    ll a,b;
    while(cin>>a>>b)
    {
        if(a<=1||b==0){cout<<1<<endl;continue;}
        ll ans=1,i,j,k,t,n,m;
        n=(ll)sqrt(a+0.5);
        for(i=2;i<=n;i++)
        {
            if(a%i==0)
            {
                t=0;
                while(a%i==0){
                    a=a/i;
                    t++;
                }
                if((i-1)%mod==0) ans=ans*(pow_mod(i,t*b+1,mod*(i-1))/(i-1))%mod;
                else ans=ans*(pow_mod(i,t*b+1,mod)-1)*pow_mod(i-1,mod-2,mod)%mod;
            }
        }
        if(a>1)
        {
            if((a-1)%mod==0)ans=ans*(pow_mod(a,b+1,mod*(a-1))/(a-1))%mod;
            else ans=ans*(pow_mod(a,b+1,mod)-1)*pow_mod(a-1,mod-2,mod)%mod;
        }
        cout<<(ans+mod)%mod<<endl;
    }
    return 0;
}

J - The Lottery

给出n , m，和m个数a[1]⋯a[m]。
求1⋯n中不被a[1]⋯a[m]中任意一个整除的数的个数。
10⩽n<2^{31}2 31 ,1⩽m⩽15
可以用容斥定理求解。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10; 
int a[20];
ll ans,n,m;
ll gcd(ll a, ll b)
{
	ll k;
	while(b)
	{
		k=b;
		b=a%b;
		a=k;
	}
	return a;
}
ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
}
void dfs(int c,int cur,int i,ll k)
{
	if(cur==c+1)
	{
		//printf("%d\n",n/k);
		if(c%2) ans-=n/k;
		else ans+=n/k;
		//printf("%d %lld %lld\n",c,ans,n/k);
		return ;
	}
	for(;i<m;i++){
		dfs(c,cur+1,i+1,lcm(k,a[i]));
	}
} 
int main()
{
	while(~scanf("%lld %lld",&n,&m))
	{
		for(int i=0;i<m;i++) scanf("%lld",&a[i]);
		ans=n;
		for(int i=1;i<=m;i++)
		{
			dfs(i,1,0,1);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

K - 组合数问题

这道题如果通过逆元暴力求解会超时,就要用个二维数组进行维护。
组合数递推公式：C(n,m)=C(n-1,m-1)+C(n-1,m)
等式左边表示从n个元素中选取m个元素，而等式右边表示这一个过程的另一种实现方法：任意选择n中的某个备选元素为特殊元素，从n中选m个元素可以由此特殊元素的分成两类情况，即m个被选择元素包含了特殊元素和m个被选择元素不包含该特殊元素。

#include <bits/stdc++.h>
#define ll long long
#define N 2050
using namespace std;
const int maxn=1e5+10;
int n,k,m,t;
int c[N][N],res[N][N];
int main()
{
    scanf("%d %d",&t,&k);
    for(int i=1;i<N;i++) c[i][0]=c[i][i]=1;
    for(int i=1;i<N;i++)
    {
        for (int j=1;j<i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
        for (int j=1;j<=i;j++)
        {
            res[i][j]=res[i][j-1];
            if (!c[i][j]) res[i][j]++;
        }
    }
    while(t--)
    {
        ll ans=0;
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++) ans+=res[i][min(i,m)];
        printf("%lld\n",ans);
    }
    return 0;
}

L - 同余方程

这题就是扩展欧几里得
扩展欧几里得详解可看这篇博客扩展欧几里得

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10; 
ll x,y,x2,y2;
void exgcd(ll a,ll b)
{
    if(b==0){
        x=1; y=0;
        return ;
    }
    exgcd(b,a%b);
    x2=x; y2=y;
    x=y2; y=x2-(a/b)*y2;
}
ll n,m;
int main()
{
	
    scanf("%lld %lld",&n,&m); 
	exgcd(n,m);
    printf("%lld\n",(x+m)%m); 
    return 0;
}