首页 > 代码库 > hdu 5943 Kingdom of Obsession 二分图匹配+素数定理

hdu 5943 Kingdom of Obsession 二分图匹配+素数定理

2024-08-18 03:50:26   226人阅读

Kingdom of Obsession

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)


Problem Description
There is a kindom of obsession, so people in this kingdom do things very strictly.

They name themselves in integer, and there are n技术分享 people with their id continuous (s+1,s+2,?,s+n)技术分享 standing in a line in arbitrary order, be more obsessively, people with id x技术分享 wants to stand at y技术分享th技术分享技术分享 position which satisfy

xmody=0技术分享


Is there any way to satisfy everyone‘s requirement?
 

 

Input
First line contains an integer T技术分享 , which indicates the number of test cases.

Every test case contains one line with two integers n技术分享 , s技术分享 .

Limits
1≤T≤100技术分享 .
1≤n≤10技术分享9技术分享技术分享 .
0≤s≤10技术分享9技术分享技术分享 .
 

 

Output
For every test case, you should output ‘Case #x: y‘, where x indicates the case number and counts from 1 and y is the result string.

If there is any way to satisfy everyone‘s requirement, y equals ‘Yes‘, otherwise y equals ‘No‘.
 

 

Sample Input
2 5 14 4 11
 

 

Sample Output
Case #1: No Case #2: Yes
 

 

Source
2016年中国大学生程序设计竞赛（杭州） 
技术分享

 

#include<bits/stdc++.h>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14const int N=2e5+10,M=1e6+10,inf=1e9+10,mod=1e9+7;const ll INF=1e18+10;int prime(int n){    if(n<=1)return 0;    if(n==2)return 1;    if(n%2==0)return 0;    int k, upperBound=n/2;    for(k=3; k<=upperBound; k+=2)    {        upperBound=n/k;        if(n%k==0)return 0;    }    return 1;}const int MAXN=1505;map<int,int>linker;map<int,int>used;vector<int>mp[MAXN];int uN;bool dfs(int u){    for(int i=0;i<mp[u].size();i++)    {        if(!used[mp[u][i]])        {            used[mp[u][i]]=1;            if(linker[mp[u][i]]==0||dfs(linker[mp[u][i]]))            {                linker[mp[u][i]]=u;                return true;            }        }    }    return false;}int hungary(){    int u;    int res=0;    linker.clear();    for(u=1;u<=uN;u++)    {        used.clear();        if(dfs(u)) res++;    }    return res;}int main(){    int T,cas=1;    scanf("%d",&T);    while(T--)    {        for(int i=0;i<MAXN;i++)           mp[i].clear();        int n,s;        scanf("%d%d",&n,&s);        if(n>s)swap(n,s);        int p=0;        for(int i=s+1; i<=s+n; i++)        {            if(prime(i))            {                p++;                if(p>=2)break;            }        }        printf("Case #%d: ",cas++);        if(p>=2)        {            printf("No\n");            continue;        }        for(int i=s+1; i<=s+n; i++)        {            for(int j=1; j<=n; j++)            {                if(i%j==0)                {                    mp[j].push_back(i);                }            }        }        uN=n;        int hh=hungary();        if(hh==n)            printf("Yes\n");        else            printf("No\n");    }    return 0;}

 

hdu 5943 Kingdom of Obsession 二分图匹配+素数定理


联系
我们