寝癖頭の解法

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

アルゴ式(beta版): C++による「整数論的アルゴリズム」補充:論理的思考力を鍛える整数問題集

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

C++による「整数論アルゴリズム」補充:論理的思考力を鍛える整数問題集

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

・11...100...0

algo-method.com

/*
C++による「整数論的アルゴリズム」補充:論理的思考力を鍛える整数問題集
11...100...0
https://algo-method.com/tasks/595
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int a,b;
    cin>>a>>b;
    cout<<(a%3==0 ? "Yes" :"No")<<endl;
    return 0;
}
・約数が奇数個

algo-method.com

/*
C++による「整数論的アルゴリズム」補充:論理的思考力を鍛える整数問題集
約数が奇数個
https://algo-method.com/tasks/355
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    long long n;
    cin>>n;
    long long ans=sqrt(n);
    cout<<ans<<endl;
    return 0;
}
・カードめくり

algo-method.com

/*
C++による「整数論的アルゴリズム」補充:論理的思考力を鍛える整数問題集
カードめくり
https://algo-method.com/tasks/356
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    long long n;
    cin>>n;
    long long ans=sqrt(n);
    cout<<n-ans<<endl;
    return 0;
}
・約数が 3 個

algo-method.com

/*
C++による「整数論的アルゴリズム」補充:論理的思考力を鍛える整数問題集
約数が 3 個
https://algo-method.com/tasks/358
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
bool is_prime(ll n){
    if(n==1 || (n!=2 && n%2==0)){
        return false;
    }
    for(ll i=3;i<=sqrt(n);i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
int main(void){
    ll n;
    cin>>n;
    ll cnt=0;
    for(ll i=2;i<=sqrt(n);i++){
        if(is_prime(i)){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}
・互いに素な約数集合

algo-method.com

/*
C++による「整数論的アルゴリズム」補充:論理的思考力を鍛える整数問題集
互いに素な約数集合
https://algo-method.com/tasks/483
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
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;
    cin>>n;
    vector<pair<ll,ll>> v=f(n);
    cout<<v.size()+1<<endl;
    return 0;
}
・N! の約数の個数

algo-method.com

/*
C++による「整数論的アルゴリズム」補充:論理的思考力を鍛える整数問題集
N! の約数の個数
https://algo-method.com/tasks/452
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll F_Legendre(ll n,ll prime){
    ll ans=0;
    while(n){
        ans+=(n/prime);
        n/=prime;
    }
    return ans;
}
int main(void){
    ll n;
    cin>>n;
    ll ans=1;
    for(int i=2;i<=n;i++){
        bool tf=true;
        for(ll j=2;j<=sqrt(i);j++){
            if(i%j==0){
                tf=false;
            }
        }
        if(tf==false){
            continue;
        }
        ll exponent=F_Legendre(n,i);
        ans*=(exponent+1);
    }
    cout<<ans<<endl;
    return 0;
}
・N! の末尾の 0 の個数

algo-method.com

/*
C++による「整数論的アルゴリズム」補充:論理的思考力を鍛える整数問題集
N! の末尾の 0 の個数
https://algo-method.com/tasks/459
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll F_Legendre(ll n,ll prime){
    ll ans=0;
    while(n){
        ans+=(n/prime);
        n/=prime;
    }
    return ans;
}
int main(void){
    ll n;
    cin>>n;
    cout<<min(F_Legendre(n,2),F_Legendre(n,5))<<endl;
    return 0;
}
・あまりが等しい 2

algo-method.com

/*
C++による「整数論的アルゴリズム」補充:論理的思考力を鍛える整数問題集
あまりが等しい 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;
}
・最大公約数の種類数 1

algo-method.com

/*
C++による「整数論的アルゴリズム」補充:論理的思考力を鍛える整数問題集
最大公約数の種類数 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;
}
・最大公約数の種類数 2

algo-method.com

/*
C++による「整数論的アルゴリズム」補充:論理的思考力を鍛える整数問題集
最大公約数の種類数 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;
}
・最大公約数の種類数 3

algo-method.com

/*
C++による「整数論的アルゴリズム」補充:論理的思考力を鍛える整数問題集
最大公約数の種類数 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;
}

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