アルゴ式(beta版)の「整数論的アルゴリズム (beta)」素因数分解からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。
Q5. 素因数分解
/* C++による「整数論的アルゴリズム (beta)」素因数分解の解答例 Q5. 素因数分解 https://algo-method.com/tasks/457 提出コードの解答例 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>> ans=f(n); for(auto a:ans){ for(ll i=0;i<a.second;i++){ cout<<a.first<<" "; } } cout<<endl; return 0; }
・Q6. メビウス関数
/* C++による「整数論的アルゴリズム (beta)」素因数分解の解答例 Q6. メビウス関数 https://algo-method.com/tasks/494 提出コードの解答例 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; } ll u(vector<pair<ll,ll>> v){ int ans=1; for(auto [i,j] : v){ if(j>1){ ans=0; }else{ ans*=-1; } } return ans; } int main(void){ ll n; cin>>n; cout<<u(f(n))<<endl; return 0; }
・Q7. √(AN) を整数にせよ
/* C++による「整数論的アルゴリズム (beta)」素因数分解の解答例 Q7. √(AN) を整数にせよ https://algo-method.com/tasks/455 提出コードの解答例 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 a; cin>>a; vector<pair<ll,ll>> v=f(a); ll ans=1; for(auto [i,j] : v){ if(j%2){ ans*=i; } } cout<<ans<<endl; return 0; }
・Q8. 互いに素な約数集合
/* C++による「整数論的アルゴリズム (beta)」素因数分解の解答例 Q8. 互いに素な約数集合 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; }
・Q9. N! の約数の個数
/* C++による「整数論的アルゴリズム (beta)」素因数分解の解答例 Q9. 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; }
・Q10. N! の末尾の 0 の個数
/* C++による「整数論的アルゴリズム (beta)」素因数分解の解答例 Q10. 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; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式(beta版)」です。
algo-method.com