アルゴ式（beta版）の「整数論的アルゴリズム」補充：論理的思考力を鍛える整数問題集からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
・11...100...0
/* 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; }
・約数が奇数個
/* 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; }
・カードめくり
/* 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 個
/* 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; }
・互いに素な約数集合
/* 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! の約数の個数
/* 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 の個数
/* 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
/* 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
/* 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
/* 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
/* 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
