『题解』Luogu P8225 「Wdoi-5」天才⑨与天才拆分

· · 题解

题目传送门

题目大意

定义一个十进制正整数为「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;
}