文章目录
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;
}
京公网安备 11010502036488号