挑戰程式設計競賽

2.5.3 圖的搜尋

#include<bits/stdc++.h>
const int MAX_V=1000+10;
using namespace std;
int n,a,b,color[MAX_V],flag=1;//n=|V| vi=a,vj=b
vector<int>G[MAX_V];
bool dfs(int now,int co){
    color[now]=co;
    for(int i=0;i<G[now].size();i++){
        if(color[G[now][i]]==co) return false;
        if(color[G[now][i]]==0&&!dfs(G[now][i],-co)) return false;
    }
    return true;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    memset(color,0,sizeof color);
    for(int i=0;i<n;i++){
        if(color[i]==0) if(!dfs(i,1)){
            printf("No\n");
            return 0;
        }
    }
    printf("Yes\n");
    return 0;
}

           

2.6.4 Uva 10006Carmichael Numbers

//快速幂加素數篩
#include<bits/stdc++.h>
const int maxn=650005;
bool is_prime[maxn];
using namespace std;
long long pow_mod(int a,int n,int mod) {
    long long res=1;
    long long t=a;
    while(n) {
        if(n&1)
            res=res*t%mod;
        t=t*t%mod;
        n>>=1;
    }
    return res;
}
void get_prime() {
    memset(is_prime,true,sizeof is_prime);
    is_prime[0]=is_prime[1]=false;
    int m=sqrt(maxn+0.5);
    for(int i=2; i<m; i++) {
        if(is_prime[i]) {
            for(int j=i*i; j<=maxn; j+=i)
                is_prime[j]=false;
        }
    }
}
int main() {
    int n;
    get_prime();
    while(~scanf("%d",&n)&&n) {
        int flag=1;
        if(is_prime[n])
            flag=0;
        if(flag)
            for(int i=2; i<n; i++) {
                if(pow_mod(i,n,n)!=i) {
                    flag=0;
                    break;
                }
            }
        if(!flag)
            printf("%d is normal.\n",n);
        else
            printf("The number %d is a Carmichael number.\n",n);
    }
    return 0;
}