数论编程实验

A - 素数筛

埃式筛法直接能够水过，注意一下从小开始枚举就行

#include <iostream>
using namespace std;
int bk[1000005];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for(int i=2;i*i<=1000000;i++)
  if(!bk[i])
  for(int j=i+i;j<=1000000;j+=i)
  bk[j]=1;
  int n;
  while(cin>>n)
  {
    if(n==0)
    break;
    for(int i=2;i;i++)
    if(!bk[n-i]&&!bk[i])
    {
      cout<<n<<" = "<<i<<" + "<<n-i<<"\n";
      break;
    }
  }
}

B - 素数筛(403了….)

C - 素数筛

还是用埃式筛法筛选出来之后用一维前缀和记录这个区间内的答案然后结果就是ans[r]-ans[l-1]

#include <iostream>
using namespace std;
int bk[1000005],ans[1000005];
int check(int x)
{
  long long sum=0;
  int p=x;
  while(p)
  {
    sum+=p%10;
    p/=10;
  }
  if(!bk[x]&&!bk[sum])
  return 1;
  else
  return 0;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for(int i=2;i*i<=1000000;i++)
  if(!bk[i])
  for(int j=i+i;j<=1000000;j+=i)
  bk[j]=1;
  for(int i=2;i<=1000000;i++)
  {
    int sum=0;
    if(check(i))
    sum=1;
    ans[i]=ans[i-1]+sum;
  }
  int t;
  cin>>t;
  while(t--)
  {
    int l,r;
    cin>>l>>r;
    cout<<ans[r]-ans[l-1]<<"\n";
  }
}

D - 素数筛

埃式筛法朴素的寻找左右边界即可

#include <iostream>
using namespace std;
int bk[1299715],ans[1299715];
int check(int x)
{
  long long sum=0;
  int p=x;
  while(p)
  {
    sum+=p%10;
    p/=10;
  }
  if(!bk[x]&&!bk[sum])
  return 1;
  else
  return 0;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for(int i=2;i*i<=1299710;i++)
  if(!bk[i])
  for(int j=i+i;j<=1299710;j+=i)
  bk[j]=1;
  int n;
  while(cin>>n)
  {
    if(n==0)
    break;
    if(!bk[n])
    cout<<0<<"\n";
    else
    {
      long long sum=0;
      for(int i=n+1;;i++)
      {
        sum++;
        if(!bk[i])
        break;
      }
      for(int i=n-1;i>=2;i--)
      {
        sum++;
        if(!bk[i])
        break;
      }
      cout<<sum<<"\n";
    }
  }
}

E - 欧几里得算法

这里注意一个结论就是gcd(a,b)与gcd(a+tb,b)的互质性相同，也就是说如果a,b互质那么a+tb与b互质，所以我们可以用已经知道的小的k-th互质数推出大的1e9-th的互质数

#include <iostream>
#include <algorithm>
using namespace std;
int ans[1000005];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,k;
  while(cin>>n>>k)
  {
    int p=0;
    for(int i=1;i<=n;i++)
    if(__gcd(i,n)==1)
    ans[++p]=i;
    cout<<ans[(k-1)%p+1]+(k-1)/p*n<<"\n";
  }
}

F - 同余定理

快速幂取余板子，余数原理的应用(a+b+c)%d=a%d+b%d+c%d,(abc)%d=a%dxb%dxc%d

#include <iostream>
using namespace std;
long long qpow(int a,int b,int mod)
{
  long long ans=1,base=a;
  while(b)
  {
    if(b&1)
    ans=ans*base%mod;
    base=base*base%mod;
    b>>=1;
  }
  return ans;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin>>t;
  while(t--)
  {
    int mod,n;
    long long sum=0;
    cin>>mod>>n;
    while(n--)
    {
      int a,b;
      cin>>a>>b;
      sum+=qpow(a,b,mod);
      sum%=mod;
    }
    cout<<sum%mod<<"\n";
  }
}

下面的题都是用了拓展欧几里得求一元线性同余方程的解所以我们需要先了解一下什么是拓展欧几里得算法
可以看我的另一篇博文拓展欧几里得算法求线性同余方程

G - 一元线性同余方程

计算线性同余方程最小的整数解，首先要找到a,b,c对应的位置，然后套用最小整数解的公式即可，中间的判断也是必不可少

#include <iostream>
using namespace std;
typedef long long ll;
void gcd(ll a,ll b,ll &d,ll &x,ll &y)
{
  if(!b)
  d=a,x=1,y=0;
  else
  gcd(b,a%b,d,y,x),y-=x*(a/b);
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ll A,B,C,k,x,y,d;
  while(cin>>A>>B>>C>>k)
  {
    if(A==0&&B==0&&C==0&&k==0)
    break;
    ll a=C;
    ll b=1LL<<k;
    ll c=B-A;
    gcd(a,b,d,x,y);
    if(c%d)
    cout<<"FOREVER\n";
    else
    {
      x=(x*(c/d))%b;
      ll b1=b/d;
      cout<<(x%b1+b1)%b1<<"\n";
    }
  }
}

H - 拓展欧几里得算法求逆元

跟上面一样甚至还比上面的简单，注意如果逆元是0那么输出为1

#include <iostream>
using namespace std;
void gcd(int a,int b,int &d,int &x,int &y)
{
  if(!b)
  d=a,x=1,y=0;
  else
  gcd(b,a%b,d,y,x),y-=x*(a/b);
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin>>t;
  while(t--)
  {
    int a,b,c=1,x,y,d;
    cin>>a>>b;
    gcd(a,b,d,x,y);
    if(c%d)
    cout<<"Not Exist\n";
    else
    {
      x=(x*(c/d))%b;
      int b1=b/d;
      cout<<(!((x%b1+b1)%b1)?1:(x%b1+b1)%b1)<<"\n";
    }
  }
}