QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#198208#6519. X Equals YEason_cyx#Compile Error//C++142.0kb2023-10-03 09:34:562023-10-03 09:34:57

Judging History

你现在查看的是最新测评结果

  • [2023-10-03 09:34:57]
  • 评测
  • [2023-10-03 09:34:56]
  • 提交

answer

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

long long x, y, A, B;

long long ceil(long long a, long long b) {
    return (a + b - 1) / b;
}

// 把 x 的 a 进制表示当成一个 b 进制数
long long gao(long long a, long long b) {
    long long ret = 0;
    for (long long t = x, p = 1; t; t /= a, p *= b) {
        // 注意!t % a >= b 是有可能的,在调用函数的地方检查
        ret += p * (t % a);
        // 超过 y 就退出,防止溢出
        if (ret > y) break;
    }
    return ret;
}

// 检查 x 的 a 进制和 y 的 b 进制表示是否相等
bool check(long long a, long long b) {
    long long xx = x, yy = y;
    while (xx && yy) {
        if (xx % a != yy % b) return false;
        xx /= a; yy /= b;
    }
    return xx == yy;
}

void solve() {
    scanf("%lld%lld%lld%lld", &x, &y, &A, &B);

    // 序列长度为 1 的情况
    if (x == y) { printf("YES\n2 2\n"); return; }

    // 序列长度为 2 的情况
    for (long long t = 1; t * t <= max(x, y); t++) if ((y - x) % t == 0) {
        long long L = 2, R = A;
        L = max(L, ceil(2 * t + x - y, t));
        L = max(L, x / (t + 1) + 1);
        L = max(L, t + 1);
        L = max(L, ((t + 1) * x - y) / (t * (t + 1)) + 1);
        L = max(L, (t * t + x - y) / t + 1);
        R = min(R, (t * B + x - y) / t);
        R = min(R, x / t);
        if (L <= R) { printf("YES\n%lld %lld\n", L, (t * L - x + y) / t); return; }
    }

    // 序列长度为 3 的情况,用双指针判断
    for (long long a = 2, b = 2; a * a <= x && a <= A; a++) {
        // 把 x 的 a 进制表示当成一个 b 进制数,如果这个数不够 y 说明 b 进制不够大
        while (gao(a, b) < y && b * b <= y && b <= B) b++;
        if (b * b > y || b > B) break;
        // 必须检查两种表示是否真的相等,因为 gao 函数中,x 的 a 进制表示里的某一位可能大于等于 b
        if (gao(a, b) == y && check(a, b)) { printf("YES\n%lld %lld\n", a, b); return; }
    }

    printf("NO\n");
}

詳細信息

answer.code: In function ‘void solve()’:
answer.code:33:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   33 |     scanf("%lld%lld%lld%lld", &x, &y, &A, &B);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/11/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x24): undefined reference to `main'
collect2: error: ld returned 1 exit status