自动搬运

查看原文

来自洛谷，原作者为

	LYqwq RP+=+∞ || 不拿钩 7 不改签名

搬运于2025-08-24 22:37:05，当前版本为作者最后更新于2022-03-22 18:22:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题目大意

定义一个十进制正整数为「$k$ 阶天才数」，当且仅当该整数的位数为 $k$ 的倍数，且每一个数位均为 $9$。

例如，$9999$ 是 $2$ 阶天才数，而 $999$ 不是 $2$ 阶天才数，但它是 $1$ 阶天才数，也是 $3$ 阶天才数。

现在给定 $t$ 个询问，每次询问给定两个正整数 $n$ 和 $k$，求能否把 $n$ 拆分成若干个 $k$ 阶天才数的和。

能则输出一行一个字符串 aya，否则输出 baka。

思路

赛时竟读错题，搞成判断 $n$ 是不是 $k$ 阶天才数了...喜提 $10$ pts。

首先是如何取这个「$k$ 阶天才数」，很容易发现最小的「$k$ 阶天才数」就可以应对所有情况。

例如，$k=3$，那么最小的「$k$ 阶天才数」就是 $999$，可以发现 $999999 \bmod 999=0$，$999999999 \bmod 999=0$，$999999999999 \bmod 999=0$······

总之，用多大的「$k$ 阶天才数」组成 $n$，都是用对应数量的最小的「$k$ 阶天才数」来组成 $n$。

用多个不同的「$k$ 阶天才数」也是如此，只需用多个最小的「$k$ 阶天才数」即可拼凑而成。

于是，我们只需判断 $n \bmod$ 最小的「$k$ 阶天才数」是否等于 $0$ 即可完成本题。

我们用一个数组 $m$ 来存储最小的「$k$ 阶天才数」，询问时直接用于判断即可。

注意，要开 long long，最小的「$10$ 阶天才数」超出了 int 范围。

代码

#include <iostream>
using namespace std;
long long t,k,n,m[15]={0,9,99,999,9999,99999,999999,9999999,99999999,999999999,9999999999,99999999999};

int main(){
    cin >> t;
    while(t--){
        cin >> k >> n;
        if(n%m[k]==0) puts("aya");
        else puts("baka");
    }
    return 0;
}