アルゴ式（beta版）: C++による「整数論的アルゴリズム」互いに素の解答例

アルゴ式（beta版）の「整数論的アルゴリズム」互いに素からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。

C++による「整数論的アルゴリズム」互いに素の解答例

僕が作成、提出したコードは、以下のとおりです。

Q2. 最大公約数パズル (2)

algo-method.com

/*
C++による「整数論的アルゴリズム」互いに素の解答例
Q2. 最大公約数パズル (2)
https://algo-method.com/tasks/533
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll> divisor(ll n){
    vector<ll> r;
    for(ll i=1;i<=sqrt(n);i++){
        if(n%i!=0){
            continue;
        }
        r.push_back(i);
        if(n/i!=i){
            r.push_back(n/i);
        }
    }
    sort(r.begin(),r.end());
    return r;
}
int main(void){
    ll g,m;
    cin>>g>>m;
    if(m%g!=0){
        cout<<-1<<endl;
        return 0;
    }
    ll num=m/g;
    vector<ll> v=divisor(num);
    ll ans=(num+1)*g;
    for(ll i : v){
        ll j=num/i;
        if(gcd(i,j)!=1){
            continue;
        }
        ans=min(ans,(i+j)*g);
    }
    cout<<ans<<endl;
    return 0;
}

Q3. 線分上の格子点の個数

algo-method.com

/*
C++による「整数論的アルゴリズム」互いに素の解答例
Q3. 線分上の格子点の個数
https://algo-method.com/tasks/474
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll GCD=gcd(abs(c-a),abs(d-b));
    cout<<GCD-1<<endl;
    return 0;
}

Q5. Ax を B の倍数に (1)

algo-method.com

/*
C++による「整数論的アルゴリズム」互いに素の解答例
Q5. Ax を B の倍数に (1)
https://algo-method.com/tasks/910
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll a,b,n;
    cin>>a>>b>>n;
    cout<<n/b<<endl;
    return 0;
}

Q6. Ax を B の倍数に (2)

algo-method.com

/*
C++による「整数論的アルゴリズム」互いに素の解答例
Q6. Ax を B の倍数に (2)
https://algo-method.com/tasks/461
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll a,b,n;
    cin>>a>>b>>n;
    ll GCD=gcd(a,b);
    cout<<n/(b/GCD)<<endl;
    return 0;
}

Q7. 3の倍数を10で割る

algo-method.com

/*
C++による「整数論的アルゴリズム」互いに素の解答例
Q7. 3の倍数を10で割る
https://algo-method.com/tasks/911
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    /*
    0
    3
    6
    9
    2
    5
    8
    1
    4
    7
    0
    ︙
    */
    cout<<10<<endl;
    return 0;
}

Q8. Aの倍数をBで割る

algo-method.com

/*
C++による「整数論的アルゴリズム」互いに素の解答例
Q8. Aの倍数をBで割る
https://algo-method.com/tasks/912
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll a,b;
    cin>>a>>b;
    cout<<b/gcd(a,b)<<endl;
    return 0;
}

設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式（beta版）」です。
algo-method.com