Codeforces Round #651 (Div. 2) B. GCD Problem

爱被打了一巴掌 2024-03-31 13:41 191阅读 0赞

Problem - 1617B - Codeforces

题意：

给定一个n，让你构造a,b,c，满足 a+b+c=n，且gcd(a,b)=c

思路：

设

c=c

b=k1*c

a=k2*c

那么有(1+k1+k2)*c=n

即c一定是n的约数，一定是多解

考虑到是构造题，我们希望把条件特殊化

令c=1，那么只需找到互质的数对(i,n-1-i)就是答案

Code：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. int n;
  5. void solve(){
  6.     cin>>n;
  7.     for(int i=2;i<n;i++){
  8.         if(__gcd(i,n-i-1)==1){
  9.             cout<<i<<" "<<n-i-1<<" "<<1<<'\n';
  10.             return;
  11.         }
  12.     }
  13. }
  14. signed main(){
  15.     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  16.     int T=1;
  17.     cin>>T;
  18.     while(T--)solve();
  19.     return 0;
  20. }

发表评论

表情：
评论列表 （有 0 条评论，191人围观）

还没有评论，来说两句吧...

相关阅读