結果

問題 No.1509 Swap!!
コンテスト
ユーザー southsidesamurai65-prog
提出日時 2026-08-18 11:54:10
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,182 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,147 ms
コンパイル使用メモリ 171,908 KB
実行使用メモリ 9,416 KB
最終ジャッジ日時 2026-08-18 11:54:22
合計ジャッジ時間 10,096 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<vector>
#include<tuple>
using namespace std;
typedef long long ll;
typedef tuple<ll,ll,ll> tlll;
//能交换任意两个相邻肯定就能实现全部序列，要实现全部序列也得能交换任意两个相邻
//最难的就是最中间的两个互换，因为两边空间更大
//扩展欧几里得算法
tlll check(ll a,ll b){
    if(a<b) swap(a,b);
    ll q=a/b;ll r=a-q*b;
    if(r==0) return make_tuple(b,1,1-q);
    auto sub=check(b,r);
    return make_tuple(get<0>(sub),get<2>(sub),get<1>(sub)-get<2>(sub)*q);
}
int main(){
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        ll n,a,b;
        cin>>n>>a>>b;
        if(a==1||b==1) {cout<<"YES"<<endl;continue;}
        if(a<b) swap(a,b);
        auto rst=check(a,b);
        if(get<0>(rst)!=1) {cout<<"NO"<<endl;continue;}
        //中间最多往前走N/2
        if(a>n/2||b>n/2) {cout<<"NO"<<endl;continue;}
        //知道问题了，前面系数有一个模的问题，我们要找最小的
        //还有问题，可以前进后退交替，那是不是理论上可以贪心，a,b都<=n/2就行，不在乎bezout系数？
        
        cout<<"YES"<<endl;
    }
    return 0;
}
0