글 읽기 - [c++] 반례가 k=1 c=1 이외에도 무엇이 있을까요 부탁드립니다

clock 2년 전 0

확장 유클리드 호제법은 끝까지 다른 분들의 코드를 보지않고 풀고 싶습니다.

k=1 c=1 케이스는 2로 고정시켜놨습니다.

답변 부탁드립니다. 감사합니다.

(수정1) lgcd 함수 추가, k와 c가 서로소가 아님을 k%c!=0으로 판단하던 것에서 lgcd(k, c)!=1로 판단하는 것으로 변경

#include <bits/stdc++.h>
using namespace std;

using LL = long long;
LL lgcd(LL a, LL b) {return b ? lgcd(b, a%b) : a;}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    int t;
    cin >> t;

    long long k, c, ktmp, ctmp, tmp, n, a, b, i, ans;
    vector<long long> q, r;
    while(t--) {
        cin >> k >> c;

        if(k==1 && c==1) {
            cout << "2\n";
            continue;
        }
        if(c==1) {
            if(k+1 <= 1e9) {
                cout << k+1 << '\n';
                continue;
            }
            else {
                cout << "IMPOSSIBLE\n";
                continue;
            }
        }
        if(k==1) {
            cout << "1\n";
            continue;
        }

        if(lgcd(k, c)!=1) {
            cout << "IMPOSSIBLE\n";
            continue;
        }

        n = 2;
        ktmp = k, ctmp = c;
        q.clear(), r.clear();
        q.push_back(0), q.push_back(0);
        r.push_back(k), r.push_back(c);
        while(ctmp>0) {
            q.push_back(ktmp/ctmp);
            r.push_back(ktmp%ctmp);

            tmp = ktmp%ctmp;
            ktmp = ctmp;
            ctmp = tmp;

            n++;
        }

        a = 1, b = q[n-2];
        for(i=0; i<n-4; i++) {
            if(i%2==0) {
                a += b*q[n-3-i];
            }
            else {
                b += a*q[n-3-i];
            }
        }

        if(n%2==0) {
            ans = -b;
            while(ans < k+1) {
                ans += k;
            }
            if(ans > 1e9) {
                cout << "IMPOSSIBLE\n";
                continue;
            }
        }
        else {
            ans = a;
            while(ans > 1e9) {
                ans -= c;
            }
            if(ans <= 0) {
                cout << "IMPOSSIBLE\n";
                continue;
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[c++] 반례가 k=1 c=1 이외에도 무엇이 있을까요 부탁드립니다

clock 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말