結果

問題 No.3501 Digit Products 2
コンテスト
ユーザー gojoxd
提出日時 2026-04-18 18:18:32
言語 C
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
AC  
実行時間 29 ms / 2,000 ms
コード長 2,418 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,488 ms
コンパイル使用メモリ 37,760 KB
実行使用メモリ 30,308 KB
平均クエリ数 10.89
最終ジャッジ日時 2026-04-18 18:18:46
合計ジャッジ時間 6,632 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 72
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>

static long long p[55];
static long long dig[55];

static long long query(int a, int b) {
    printf("? %d %d\n", a, b);
    fflush(stdout);
    long long resp;
    scanf("%lld", &resp);
    return resp;
}

/* integer square root via Newton's method */
static long long isqrt_ll(long long n) {
    if (n <= 0) return 0;
    long long r = n, s = (n + 1) >> 1;
    while (s < r) { r = s; s = (s + n/s) >> 1; }
    return r;
}

int main(void) {
    int N;
    scanf("%d", &N);

    int last = N - 1;  /* anchor = most significant digit, always >= 1 */

    int nz[55], nz_cnt = 0;
    for (int i = 0; i < last; i++) {
        p[i] = query(i, last);         /* d[i] * d[last] */
        if (p[i] > 0)
            nz[nz_cnt++] = i;
    }

    if (nz_cnt >= 2) {
        /* At least 2 non-anchor digits are nonzero: use N-th query to unlock anchor */
        int is = nz[0], js = nz[1];
        long long q = query(is, js);   /* d[is] * d[js] */
        /* d[last]^2 = p[is]*p[js] / q */
        long long d_last = isqrt_ll(p[is] * p[js] / q);

        for (int i = 0; i < last; i++)
            dig[i] = (p[i] == 0) ? 0 : p[i] / d_last;
        dig[last] = d_last;

        printf("! ");
        for (int i = last; i >= 0; i--)
            printf("%lld", dig[i]);
        printf("\n");
        fflush(stdout);

    } else if (nz_cnt == 1) {
        /* Only one non-anchor digit is nonzero: check if its product with anchor factors uniquely */
        int is = nz[0];
        long long prod = p[is];
        int pair_cnt = 0, pair_a = 0, pair_b = 0;
        for (int a = 1; a <= 9; a++) {
            if (prod % a == 0) {
                int b = (int)(prod / a);
                if (b >= 1 && b <= 9) {
                    pair_cnt++;
                    pair_a = a;
                    pair_b = b;
                }
            }
        }
        if (pair_cnt == 1) {
            for (int i = 0; i < last; i++)
                dig[i] = (i == is) ? pair_a : 0;
            dig[last] = pair_b;

            printf("! ");
            for (int i = last; i >= 0; i--)
                printf("%lld", dig[i]);
            printf("\n");
            fflush(stdout);
        } else {
            printf("! -1\n");
            fflush(stdout);
        }

    } else {
        /* All non-anchor digits are 0, anchor is unknown -> ambiguous */
        printf("! -1\n");
        fflush(stdout);
    }

    return 0;
}
0