寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

アルゴ式(beta版): C++による「整数論的アルゴリズム (beta)」最大公約数の解答例

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

C++による「整数論アルゴリズム (beta)」最大公約数の解答例

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

Q3. 最大公約数 (正方形切り分け)

algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」最大公約数の解答例
Q3. 最大公約数 (正方形切り分け)
https://algo-method.com/tasks/487
提出コードの解答例
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<<gcd(a,b)<<endl;
    return 0;
}
・Q4. 最小公倍数 (正方形を作れ)

algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」最大公約数の解答例
Q4. 最小公倍数 (正方形を作れ)
https://algo-method.com/tasks/475
提出コードの解答例
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<<lcm(a,b)<<endl;
    return 0;
}
・Q5. 公約数の個数

algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」最大公約数の解答例
Q5. 公約数の個数
https://algo-method.com/tasks/496
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
//配列A[0]~A[N]の最大公約数GCDを設定し,
//その約数の個数を出力する解法.
#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);
        }
    }
    return r;
}
int main(void){
    ll n;
    cin>>n;
    vector<ll> a(n);
    ll GCD=0;
    for(ll i=0;i<n;i++){
        cin>>a[i];
        GCD=gcd(GCD,a[i]);
    }
    vector<ll> v=divisor(GCD);
    cout<<v.size()<<endl;
    return 0;
}
・Q6. あまりが等しい (2)

algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」最大公約数の解答例
Q6. あまりが等しい (2)
https://algo-method.com/tasks/551
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
//問題"あまりが等しい (1)"の提出コードを応用.
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll> divisor(ll n){
    vector<ll> v;
    for(ll i=1;i<=sqrt(n);i++){
        if(n%i!=0){
            continue;
        }
        v.push_back(i);
        if(n/i!=i){
            v.push_back(n/i);
        }
    }
    sort(v.begin(),v.end());
    return v;
}
int main(void){
    ll n;
    cin>>n;
    ll GCD=0;
    vector<ll> a(n);
    cin>>a[0];
    for(ll i=1;i<n;i++){
        cin>>a[i];
        GCD=gcd(GCD,abs(a[i]-a[i-1]));
    }
    vector<ll> ans=divisor(GCD);
    cout<<ans.size()<<endl;
    return 0;
}
・Q7. りんごとみかん

algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」最大公約数の解答例
Q7. りんごとみかん
https://algo-method.com/tasks/500
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll> divisor(ll n){
    vector<ll> v;
    for(ll i=1;i<=sqrt(n);i++){
        if(n%i!=0){
            continue;
        }
        v.push_back(i);
        if(n/i!=i){
            v.push_back(n/i);
        }
    }
    sort(v.begin(),v.end());
    return v;
}
int main(void){
    ll a,b,r,s;
    cin>>a>>b>>r>>s;
    ll GCD=gcd(a-r,b-s);
    ll ans=-1;
    vector<ll> v=divisor(GCD);
    for(auto i : v){
        if(i>max(r,s)){
            ans=i;
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}
・Q8. バスの同時発車

algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」最大公約数の解答例
Q8. バスの同時発車
https://algo-method.com/tasks/511
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll a,b,k;
    cin>>a>>b>>k;
    ll meet=lcm(a,b);
    cout<<meet*k<<endl;
    return 0;
}
・Q9. 最大公約数の種類数 (1)

algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」最大公約数の解答例
Q9. 最大公約数の種類数 (1)
https://algo-method.com/tasks/530
提出コードの解答例
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){
            r.push_back(i);
            if(i*i!=n){
                r.push_back(n/i);
            }
        }
    }
    sort(r.begin(),r.end());
    return r;
}
int main(void){
    ll n,m;
    cin>>n>>m;
    if(m==1){
        cout<<1<<endl;
        return 0;
    }
    vector<ll> v=divisor(m);
    cout<<v.size()<<endl;
}
Q10. 最大公約数の種類数 (2)

algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」最大公約数の解答例
Q10. 最大公約数の種類数 (2)
https://algo-method.com/tasks/521
提出コードの解答例
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){
            r.push_back(i);
            if(i*i!=n){
                r.push_back(n/i);
            }
        }
    }
    sort(r.begin(),r.end());
    return r;
}
int main(void){
    ll n,m;
    cin>>n>>m;
    ll ans=0;
    const auto &vec=divisor(m);
    for(auto i : vec){
        if(n*i<=m){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}
・Q11. 最大公約数の種類数 (3)

algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」最大公約数の解答例
Q11. 最大公約数の種類数 (3)
https://algo-method.com/tasks/578
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
//f := 素因数分解の関数
vector<pair<ll,ll>> f(ll n){
    vector<pair<ll,ll>> v;
    for(ll i=2;i<=sqrt(n);i++){
        if(n%i!=0){
            continue;
        }else{
            ll cnt=0;
            while(n%i==0){
                cnt++;
                n/=i;
            }
            v.push_back(pair(i,cnt));
        }
    }
    if(n!=1){
        v.push_back(pair(n,1));
    }
    return v;
}
int main(void){
    ll n,m;
    cin>>n>>m;
    const auto& v=f(m);
    ll ans=1;
    for(auto [i,j] : v){
        ll k=j/n;
        ans*=(k+1);
    }
    cout<<ans<<endl;
    return 0;
}
・Q12. 黒板ゲーム (1)

algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」最大公約数の解答例
Q12. 黒板ゲーム (1)
https://algo-method.com/tasks/498
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll a,b,k;
    cin>>a>>b>>k;
    if(k>max(a,b)){
        cout<<"No"<<endl;
    }else{
        ll GCD=gcd(a,b);
        if(k%GCD==0){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
    return 0;
}

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