이분 도 일치-HDU 5943

링크:http://acm.hdu.edu.cn/showproblem.php?pid=5943
4.567917.제목:주어진 s,n,s+1,s+2,...,s+n 이라는 n 개 수 를 1,2,3,n 의 위치 에 놓 을 수 있 는 지 판단 합 니 다(x 가 y 에 놓 을 수 있다 면 x 를 만족 시 켜 야 합 니 다. mod y=0 ）
4.567917.분석:이 문 제 는 매우 뚜렷 한 이분 도 일치 이지 만 n 은 1E9 의 크기 이기 때문에 우 리 는 직접 할 수 없다.그러나 우 리 는 만약 에[s+1,s+n]안에 2 개의 소수 가 있다 면 만족 하지 않 을 것 이라는 것 을 발견 했다.(소 수 는 위치 1 에 만 놓 을 수 있 고 2 개의 소 수 는 반드시 충돌 할 것 이다)그래서 우 리 는 이 를 이용 하여 n 의 범 위 를 좁 힐 수 있다.이 거 리 는 1000(실제 500 정도?)이 라 고 추측 할 수 있다.그러면 우리 가 처리 한 n 의 범 위 는 크게 좁 혀 질 것 이다
AC 코드:

/*************************************************************************
    > File Name: K.cpp
    > Author: Akira
    > Mail: [email protected]
    > Created Time: 2017 05 05      21 08 56 
 ************************************************************************/

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define Sqr(a) ((a)*(a))

using namespace std;

#define MaxN 2000
#define MaxM MaxN*20
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
const int mod = 1e9+7;
const int eps = 1e-8;
#define bug cout << 88888888 << endl;

int T;
int n,s,x;

struct Edge
{
    int u, v, next;
}edge[MaxM];
int cont, head[MaxN];

void add(int u, int v)
{
    edge[cont].v = v;
    edge[cont].next = head[u];
    head[u] = cont++;
}

void init()
{
    cont = 0;
    MST(head, -1);
}

int match[MaxN];
bool check[MaxN];

bool DFS(int u)
{
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v = edge[i].v;
        if(!check[v])
        {
            check[v] = true;
            if(match[v]==-1 || DFS(match[v]))
            {
                match[v] = u;
                match[u]=  v;
                return true;
            }
        }
    }
    return false;
}

int Hungarian()
{
    int ans = 0;
    MST(match, -1);
    for(int i=1;i<=x;i++)
    {
        if(match[i] == -1)
        {
            CLR(check);
            if(DFS(i)) ans++;
        }
    }
    //for(int i=1;i<=n;i++) cout << i << " - " << match[i] << endl;
    return ans;
}


int main()
{
    scanf("%d", &T);
    for(int t=1;t<=T;t++)
    {
        scanf("%d%d", &n, &s);
        printf("Case #%d: ",  t);
        int sta = max(s,n);
        if(s==0||s==1||s==2) puts("Yes");
        else if( (s+n - sta )>=600) puts("No");
        else 
        {
            init();
            x = s+n - sta;
            for(int i=sta+1; i<=s+n; i++)
            {
                for(int j=1;j<=x;j++)
                {
                    if(i%j==0) add(i-sta+x, j), add(j, i-sta+x);
                }
            }
            int cnt = Hungarian();
            if(cnt==x) puts("Yes");
            else puts("No");    
        }
    }
}