アルゴ式（beta版）の「整数論的アルゴリズム (beta)」最大公約数からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
Q3. 最大公約数 (正方形切り分け)
/* 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. 最小公倍数 (正方形を作れ)
/* 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. 公約数の個数
/* 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)
/* 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. りんごとみかん
/* 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. バスの同時発車
/* 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)
/* 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)
/* 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)
/* 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)
/* 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
