1月14日

构造题训练

Problem - B - Codeforces

Problem - D - Codeforces二分

Problem - C - Codeforces优先队列

下午

小希的迷宫 - HDU 1272 - Virtual Judge

并查集判环典题，但是有细节，n=0&&m=0输出yes(唐)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
//typedef unsigned __int128 LL;
const int N=1e5+10,M=5e5+10,inf=1e16,mod=1e8;
int n,m;
int fa[N];
int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void solve() {
    while(cin>>n>>m){
        int f=1;
        int bian=1;
        if(n==-1&&m==-1) break;
        for(int i=0;i<N;i++) fa[i]=i;
        if(n==0&&m==0){
            cout<<"Yes"<<endl;
            continue;
        }
        set<int> se;
        se.insert(n);
        se.insert(m);
        fa[n]=m;
        while(1){
            int u,v;
            cin>>u>>v;
            if(u==0&&v==0) break;
            bian++;
            se.insert(v);
            se.insert(u);
            int fx=find(u);
            int fy=find(v);
            if(fx==fy){
                f=0;
            }
            else fa[fx]=fy;
        }
        if(!f) cout<<"No"<<endl;
        else {
            if(bian==se.size()-1) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//    int _;
//    cin >> _;
//    while (_--)
    solve();
    return 0;
}

Aladdin and the Flying Carpet - LightOJ 1341 - Virtual Judge

题意：求出1e12内质因子的个数

思路：太唐，有查询，所以不能每次O（\sqrt{n} ）, 所以先预处理筛出\sqrt{n} 内所有素数就行了

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
//typedef unsigned __int128 LL;
const int N=1e6+10,M=5e5+10,inf=1e16,mod=1e8;
int tt=0;
int vis[N];  //划掉合数
int prim[N]; //记录质数
int cnt; //质数个数

void get_prim(int n) { //欧拉筛法-----O(N)
    vis[1]=1;
    for (int i = 2; i <= n; i++) {//越界中断
        if (!vis[i]) prim[++cnt] = i;
        for (int j = 1; i * prim[j] <= n; j++) {//乘以已经记录的数，越界中断，开筛
            vis[i * prim[j]] = 1;
            if (i % prim[j] == 0) break;//整除中断，保证被最小的质因子prim[j]划掉
        }
    }
}
void solve() {
    int a,b;
    cin>>a>>b;
    cout<<"Case "<<++tt<<": ";
    if(b*b>a){
        cout<<0<<endl;
        return;
    }
    int ans=1;
    int t=a;
    for(int i=1;i<=cnt&&prim[i]*prim[i]<=a;i++){
        if(t==0) break;
        if(t%prim[i]==0){
            int p=0;
//            cout<<prim[i]<<endl;
            while(t%prim[i]==0){
                p++;
                t/=prim[i];
            }
            ans*=(p+1);
        }
    }
    if(t>1) ans*=2;
    ans/=2;
    for(int i=1;i<b;i++){
        if(a%i==0) ans--;
    }
    cout<<ans<<endl;
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    get_prim(N);
    int _;
    cin >> _;
    while (_--)
        solve();
    return 0;
}