头像

苏醒


访客:329

离线:10小时前


活动打卡代码 AcWing 872. 最大公约数

苏醒
10小时前
#include<iostream>
using namespace std;
int gcb(int a,int b){
    return b?gcb(b, a%b): a; //b == 0      gcb(a,0) = a 否则就辗转相除
}
int main(){
    int n;
    cin >>n;
    while(n--){
        int a,b;
        cin >> a>> b;
        cout << gcb(a,b)<<endl;
    }
    return 0;

}


活动打卡代码 AcWing 871. 约数之和

苏醒
11小时前
#include<iostream>
#include<unordered_map>
using namespace std;
const int mod = 1e9+7;
unordered_map<int,int> primes;
int main(){
    int n;
    cin>> n;
    while(n--){
        int a;
        cin >>a;
        for(int i = 2; i <= a/i;i++){
            while(a % i == 0){
                primes[i]++;
                a = a/i;
            }
        }
        if(a > 1) primes[a]++;//大于sqrt(a)的质因子 👀限制性条件为 i^2 <= a

    }
    long long res = 1;
    for(auto prime:primes) {
        int p = prime.first, a = prime.second;
        long long t = 1;
        while(a--) t = (p * t + 1)%mod;
        res = res * t % mod;
    }
    cout << res<<endl;
    return 0;

}


活动打卡代码 AcWing 870. 约数个数

苏醒
11小时前
#include<iostream>
#include<unordered_map>
using namespace std;
const int mod = 1e9+7;
unordered_map<int,int> primes;
int main(){
    int n;
    cin>> n;
    while(n--){
        int a;
        cin >>a;
        for(int i = 2; i <= a/i;i++){
            while(a % i == 0){
                primes[i]++;
                a = a/i;
            }
        }
        if(a > 1) primes[a]++;//大于sqrt(a)的质因子 👀限制性条件为 i^2 <= a

    }
    long long res = 1;
    for(auto prime:primes) res = res * (prime.second+1)%mod; //乘完超范围了再mod
    cout << res<<endl;
    return 0;

}


活动打卡代码 AcWing 869. 试除法求约数

苏醒
11小时前
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> Did(int n){
    vector<int> res;
    for(int i = 1; i <= n/i;i++){
        if(n % i == 0){
            res.push_back(i);
            if(i != n/i ) res.push_back(n/i);
        }
    }//sart(n)
    sort(res.begin(),res.end());//每个数的约数个数是log n 此句复杂度logn loglog n ~= log n
    return res;
}

int main(){
    int n;
    cin >> n;
    while(n--){
        int a;
        cin >>a;
        auto ans = Did(a);
        for(auto t:ans) cout<<t<< ' ';
        cout<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 868. 筛质数

苏醒
12小时前

朴素(埃氏)筛法

时间复杂度:O(n loglog n) ~= O(n)

#include<iostream>
using namespace std;
const int N = 1000010;
int n;
int prime[N],cnt;
bool st[N];
void gerP(int n){
    for(int i = 2; i <= n;i++){
        if(!st[i]) {
            prime[cnt++] = i;
            for(int j = i + i; j <= n;j += i){//删除1~n间的数
                st[j] = true;
            }
        }
    }
}

线性筛法

不太明白原理 先不细究

void gerP(int n){
    for(int i = 2; i <= n;i++){
        if(!st[i]) 
            prime[cnt++] = i;
        for(int j = 0;prime[j] <= n / i;j++){
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
        }
}
int main(){
    cin >> n;
    gerP(n);
    cout << cnt <<endl;
    return 0;
}


活动打卡代码 AcWing 867. 分解质因数

苏醒
13小时前
#include<iostream>
using namespace std;
void divide(int a){
    for(int i = 2;i <= a / i;i++){

        if(a % i == 0){
            int s = 0;
            while(a%i == 0){
                a  = a / i;
                s++;
            }
            printf("%d %d\n",i, s);
        }
    }
    if(a > 1) printf("%d %d\n",a, 1);//大于sqrt(n) 的质因子
    puts("");
}

int main(){
    int n;
    cin >> n;
    while(n--){
        int a;
        cin >>a;

        divide(a);
    }
    return 0;
}



苏醒
13小时前
#include<iostream>
using namespace std;

bool isPrime(int a){
    if(a < 2) return false;
    for(int i = 2;i <= a / i;i++){
        if(a % i == 0) return false;

    }
    return true;

}
int main(){
    int n;
    cin >>n;
    int nn= n;
    while(nn--)
    {
        int a;
        cin >> a;
        if(isPrime(a)) cout << "Yes"<<endl;
        else cout << "No"<<endl;
    }
    return 0;
}



苏醒
15小时前
//临接表存储
//男女配对思想
//
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, M = 100010;
int n1,n2,m;
int h[N],e[M],ne[M],idx;
int match[N];
bool st[N];
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
bool find(int u){//直接搜连接的边儿 找到u的对象
    for(int i = h[u]; i != -1; i = ne[i]){
        int x = e[i];
        if(!st[x]) {
            st[x] = true;

            if(match[x] == 0 || find(match[x]))//对面没对象 或者 能帮对面找到对象
                {match[x] = u;
                return true;}
        }
    }
    return false;
}
int main(){
    cin >> n1>>n2>>m;
    memset(h, -1, sizeof h);
    while(m--){
        int a,b;
        cin >>a>>b;
        add(a,b);
    }
    int res = 0;
    for(int i = 1;i <=n1;i++){
        memset(st, false, sizeof st);
        if(find(i)) res++;
    }
    cout << res <<endl;
    return 0;
}



苏醒
18小时前
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
int n,m;
int h[N],e[2*N],ne[2*N],idx;
int color[N];
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
bool dfs(int u,int c){
    color[u] = c;
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(color[j] == 0)
        {
            if(!dfs(j,3-c)) return false;
        }else if(color[j] == c) return false;

    }
    return true;
}

int main(){
    cin >> n>> m;
    memset(h, -1, sizeof h);
    while(m--){
        int a,b;
        cin >> a>>b;
        add(a,b), add(b,a);
    }
    int flag = true;
    for(int i = 1;i <= n;i++){
        if(color[i] == 0){
            if(!dfs(i,1)) flag = false;
        }
    }
    if(flag) puts("Yes");
    else puts("No");
    return 0;


}



苏醒
18小时前
//dist ∞
//找集合外最近点
//更新 其他点
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510,M = 100010,INF = 0x3f3f3f3f;
int n,m;
int g[N][N];
bool st[N];
int dist[N];
int prim(){
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    for(int i = 0; i < n;i++){
        int t = -1;
        for(int j = 1; j<=n ; j++){
            if(!st[j] &&(t == -1 || dist[t] > dist[j]))
                t = j;
        }
        if(i && dist[t] == INF) return INF;
        if(i) res += dist[t];
        st[t] = true;
        for(int j = 1; j <= n;j++) dist[j] = min(dist[j], g[t][j]);

    }
    return res;
}


int main(){
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    int mm = m;
    while(mm--){
        int a,b,c;
        cin >> a>>b>>c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int t = prim();
    if(t == INF) puts("impossible");
    else cout << t<<endl;
}