寝癖頭の解法

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

paizaラーニング: C++による「素数メニュー」問題集: 最小公倍数

paizaラーニングのレベルアップ問題集「素数メニュー」からの出典です。
paiza.jp
C++による「素数メニュー」問題集: 最小公倍数と、それらの提出コードの解答例です。

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

・STEP: 1 素因数分解

/*
C++による「素数メニュー」問題集: 最小公倍数
STEP: 1 素因数分解
https://paiza.jp/works/mondai
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> f(int n){
    vector<pair<int,int>> v;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i!=0){
            continue;
        }else{
            int 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){
    int n;
    cin>>n;
    vector<pair<int,int>> ans=f(n);
    for(auto a:ans){
        for(int i=0;i<a.second;i++){
            cout<<a.first<<endl;
        }
    }
    return 0;
}

・STEP: 2 約数の個数

/*
C++による「素数メニュー」問題集: 最小公倍数
STEP: 2 約数の個数
https://paiza.jp/works/mondai
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> f(int n){
    vector<pair<int,int>> v;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i!=0){
            continue;
        }else{
            int 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){
    int n;
    cin>>n;
    vector<pair<int,int>> vp=f(n);
    int ans=1;
    for(auto a:vp){
        ans*=(a.second+1);
    }
    cout<<ans<<endl;
    return 0;
}

・STEP: 3 最大公約数

/*
C++による「素数メニュー」問題集: 最小公倍数
STEP: 3 最大公約数
https://paiza.jp/works/mondai
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    int i;
    while(b>0){
        i=a%b;
        a=b;
        b=i;
    }
    return a;
}
int main(void){
    int n;
    cin>>n;
    vector<int> a(n);
    cin>>a[0];
    int ans=a[0];
    for(int i=1;i<n;i++){
        cin>>a[i];
        ans=gcd(ans,a[i]);
    }
    cout<<ans<<endl;
    return 0;
}

・FINAL問題: 最小公倍数

/*
C++による「素数メニュー」問題集: 最小公倍数
FINAL問題: 最小公倍数
https://paiza.jp/works/mondai
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll gcd(ll a,ll b){
    ll i;
    while(b>0){
        i=a%b;
        a=b;
        b=i;
    }
    return a;
}
ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}
int main(void){
    ll n;
    cin>>n;
    vector<ll> a(n);
    cin>>a[0];
    for(ll i=1;i<n;i++){
        cin>>a[i];
    }
    ll ans=1;
    for(ll i=0;i<n;i++){
        ans=lcm(ans,a[i]);
    }
    cout<<ans<<endl;
    return 0;
}

paizaラーニングのレベルアップ問題集については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
また授業や研修、教材などにも利用できるそうです。