算法入门-简单数论

BGN41 判断质数

//
// Created by XIAOBAI on 2026/5/21.
//判断质数

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
bool is_prime(ll a) {
    for (ll i=2;i*i<=a;i++) {
        if (a%i==0) return false;
    }
    return true;
}
void solve() {
    ll n;
    cin>>n;
    if (is_prime(n)) {
        cout<<"Yes"<<endl;
    }else {
        cout<<"No"<<endl;
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN42 分解质因数

//
// Created by XIAOBAI on 2026/5/21.
//分解质因数

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll n=1;
    cin>>n;
    for (int i=2;i*i<=n;i++) {
        //cout<<i<<" "<<n<<'\n';注意下边根本不需要判断质数！！！
        //因为是从2开始，到i会把所有因数为i的合数除尽！
            while (n%i==0) {
                cout<<i<<" ";
                n/=i;
            }
    }
    if (n!=1) cout<<n;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN43 GCD和LCM

//
// Created by XIAOBAI on 2026/5/21.
//GCD和LCM

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
#include <numeric>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
ll GCD(ll a,ll b) {
    return b==0?a:GCD(b,a%b);
}
ll LCM(ll a,ll b) {
    return a/(GCD(a,b)*b);
}
void solve() {
    ll a,b;
    cin>>a>>b;
    //cout<<__gcd(a,b)<<" "<<lcm(a,b);
    cout<<GCD(a,b)<<" ";
    cout<<LCM(a,b);

}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN44 几乎是质数（埃氏筛法）

//
// Created by XIAOBAI on 2026/5/21.
//几乎是质数（埃氏筛法）
#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
#include <numeric>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}

void solve() {
    int n;
    cin>>n;
    vector<int> a(n+1,0);
    for(int i=2;i<=n;i++) {
        //a[i]==0 说明他就是质数！
        //这是因为从2开始向后遍历，如果a[i]==0则说明从2到这里没有一个数是它的因数！因此它一定是质数
        if (a[i]==0) {
            for (int j=i;j<=n;j+=i) {
                a[i]++;
            }
        }
    }
    ll ans=0;
    for (int i=1;i<=n;i++) {
        if (a[i]==2) ans++;
    }
    cout<<ans;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN45 1=N（本质分解质因数

//
// Created by XIAOBAI on 2026/5/21.
//1=N（本质分解质因数

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll n=1,ans=0;
    cin>>n;
    for (int i=2;i*i<=n;i++) {
        //cout<<i<<" "<<n<<'\n';
            while (n%i==0) {
                ans+=i;
                n/=i;
        }
    }
    if (n!=1) ans+=n;
    cout<<ans;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN46 复杂的最大公约数

//
// Created by XIAOBAI on 2026/5/21.
//复杂的最大公约数

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
bool is_prime(ll a) {
    for (ll i=2;i*i<=a;i++) {
        if (a%i==0) return false;
    }
    return true;
}
void solve() {
    string a,b;
    cin>>a>>b;
    if (a==b) cout<<a;
    else cout<<1;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN47 小红和小紫的取素因子游戏

//
// Created by XIAOBAI on 2026/5/21.
//小红和小紫的取素因子游戏

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll n,cnt=0;
    cin>>n;
    for (int i=2;i*i<=n;i++) {
        while (n%i==0) {
            cnt++;
            n/=i;
        }
        if(n==1)break;
    }
    if (n>1) cnt++;
    cout << (cnt % 2 ? "kou\n" : "yukari\n");

}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }

}

BGN48 矩形游戏

//
// Created by XIAOBAI on 2026/5/21.
//矩形游戏

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll n;
    cin>>n;
    ll ans=n;
    for (ll i=2;i*i<n;i++) {
        if (n%i==0) {
            ans+=n/i;
            //cout<<ans<<" ";
            n/=i;
            //cout<<n<<"! ";
            i=1;
        }
    }
    ans+=1;
    cout<<ans;


}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN49 游游的最小公倍数

//
// Created by XIAOBAI on 2026/5/21.
//游游的最小公倍数

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
#include <numeric>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll n;
    cin>>n;
    ll a=n/2,b=n-a;
    while(a>1&&b>1&&a==b||gcd(a,b)!=1) {a--;b++;}
    //lcm尽可能大代表gcd要尽可能小，且a，b尽可能靠近n/2
    //但是a,b不能小于1，条件整合后如上所示
    cout<<a<<" "<<b<<'\n';
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }

}

BGN50 小红走网格

//
// Created by XIAOBAI on 2026/5/21.
//小红走网格

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
#include <numeric>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll x,y,a,b,c,d;
    cin>>x>>y>>a>>b>>c>>d;
    if (y%gcd(a,b)==0&&x%gcd(c,d)==0) {
        cout<<"YES"<<'\n';
    }else {
        cout<<"NO"<<'\n';
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }

}