淘先锋技术网

首页 1 2 3 4 5 6 7

2018 ACM-ICPC 中国大学生程序设计竞赛线上赛 B. Goldbach

传送门 ： 题目链接
这道题一看就不简单，因为当时通过率还不足5%，后来仔细分析了一下，显而易见不能开数组，用map也是超限，只能一个一个判断是不是素数，问题就出在了两个地方。1.忘了用 unsigned long long ，2.不知道 Miller-Rabin素数检测算法，当时想的是用一个很水的筛法 
bool su(long long a)
{
    if(a == 2 || a == 3)return 1;
    if(a %  6!=1 && a % 6 != 5) return 0;
    for(int i = 5; i <= sqrt(a); i += 6)
        if(a%i == 0||a%(i + 2)==0)return 0;
    return 1;
}

放平时做水题的时候还能用。。但是这次了解到了新的筛法
关于实现过程目前不深入了解了，等省赛回来再仔细分析，先当成模板用着（应该不会出问题吧。。 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
typedef unsigned long long ll;
ll ModMul(ll a,ll b,ll n)//快速积取模 a*b%n
{
    ll ans=0;
    while(b)
    {
        if(b&1)
        ans=(ans+a)%n;
        a=(a+a)%n;
        b>>=1;
    }
    return ans;
}
ll ModExp(ll a,ll b,ll n)//快速幂取模 a^b%n
{
    ll ans=1;
    while(b)
    {
        if(b&1)
        ans=ModMul(ans,a,n);
        a=ModMul(a,a,n);
        b>>=1;
    }
    return ans;
}
bool miller_rabin(ll n)//Miller-Rabin素数检测算法
{
    ll i,j,a,x,y,t,u,s=10;
    if(n==2)
    return true;
    if(n<2||!(n&1))
    return false;
    for(t=0,u=n-1;!(u&1);t++,u>>=1);//n-1=u*2^t
    for(i=0;i<s;i++)
    {
        a=rand()%(n-1)+1;
        x=ModExp(a,u,n);
        for(j=0;j<t;j++)
        {
            y=ModMul(x,x,n);
            if(y==1&&x!=1&&x!=n-1)
            return false;
            x=y;
        }
        if(x!=1)
        return false;
    }
    return true;
}
int main()
{
    int t;
    unsigned long long n, i;
    scanf("%d",&t);
    while(t --)
    {
        scanf("%llu",&n);

        for(i = 1; i <= n; i ++)
        {
            if(miller_rabin(i) && miller_rabin(n - i))
                break;
        }
        printf("%lld %lld\n",i,n-i);
    }
    return 0;
}