• 欢迎光临~

CF1542B Plus and Multiply

开发技术 开发技术 2022-10-14 次浏览

CF1542B Plus and Multiply - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

(T = {a^x +yb text{ } vert text{ } x, y in N})(S) 相等。

证明:

  • (S subseteq T):显然有 (1 in T)。然后有 ((a^x+yb) times a = a^{x+1} + (ay)b)((a^x + yb) + b = a^{x+1} + (y+1)b)
  • (T subseteq S)(a^x + yb) 可以由 (1)(x)(a) 再加 (y)(b) 得到。

因此 (S = T)

那么问题可以转化为 (n) 是否可以表示为 (a^x + yb),其中 (x, y in N)

容易发现当 (a ne 1) 时,(x) 的范围很小。枚举 (x) 即可。然后检验 (y) 是否为 (n - a^x) 的因数。

(a = 1) 时容易特判:只需要检验 (n bmod b = 1)(b = 1) 即可(注意 (X bmod 1 = 0))。

单组数据 (mathcal{O}(log n))

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2022-10-14 01:41:35 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2022-10-14 01:52:57
 */

#include <bits/stdc++.h>
#define int long long

inline int read() {
    int x = 0;
    bool flag = true;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            flag = false;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    if(flag)
        return x;
    return ~(x - 1);
}

signed main() {
    int T = read();
    while (T--) {
        int n = read(), a = read(), b = read();
        if (a == 1) {
            if (b == 1 || n % b == 1)
                puts("Yes");
            else
                puts("No");
            continue;
        }

        bool fl = false;
        for (int X = 1; X <= n; X *= a) {
            if ((n - X) % b == 0) {
                fl = true;
                break;
            }
        }

        puts(fl ? "Yes" : "No");
    }
    return 0;
}
程序员灯塔
转载请注明原文链接:CF1542B Plus and Multiply
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com