一起开心暑假集训第一周限时训练 2020/7/5

vjudge试题集链接

A - Goldbach’s Conjecture POJ - 2262

试题链接：
线性筛先预处理，然后判断就行

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1000000;
int prime[maxn+3];
int isprime[maxn+4];
void Prime(int N)
{
   
	memset(isprime,1,sizeof(isprime));
	isprime[1]=0;
	int cnt=0;
	for(int i=2;i<=N;i++)
	{
   
		if(isprime[i])prime[++cnt]=i;
		for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
		{
   
			isprime[i*prime[j]]=0;
			if(i%prime[j]==0)break;
		 } 
	}
}
int main()
{
   
	int n;
	Prime(maxn);
	while(cin>>n)
	{
   
		if(n==0)break;
		for(int i=3;i<=n;i++)
		{
   
			if(isprime[i]!=0&&isprime[n-i]!=0)
			{
   
				printf("%d = %d + %d\n",n,i,n-i);
				break;
			}
		}
	}
	return 0;
}

B - 同余方程 计蒜客 - T2010

试题链接：
求逆元裸题，好像是noip原题

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得算法
{
   
    if(b==0)
    {
   
        x=1;
		y=0;
        return a;  //到达递归边界开始向上一层返回
    }
    ll gcd=exgcd(b,a%b,x,y);
    ll y1=y;    //把x y变成上一层的
    ll x1=x;
    y=x1-(a/b)*y1;
    x=y1;
    return gcd;     //得到a b的最大公因数
}
ll inv(ll a,ll mod){
   
	ll x,y;
	ll gcd=exgcd(a,mod,x,y);
	if(gcd!=1)return -1;
	else return (x+mod)%mod; 
}

int main()
{
   
	ll a,b;
	cin>>a>>b;
	cout<<inv(a,b)<<endl;
	return 0;
}

C - Tr A HDU - 1575

试题链接：
题解

D - C Looooops POJ - 2115

试题链接：
题解：