题目分析
NNN 最大为 1020000010 ^ {200000}10200000,显然超出整数正常处理范围,可以使用高精度除法但这题有更便捷的做法。
以下给出本题的部分方法。
方法一:999 的倍数含有性质,如果一个数是 999 的倍数,它们的各位数字之和一定是9的倍数。这是因为一个数被9整除,当且仅当它的各位数字之和被9整除。
方法二:利用同余性质,N % 9 == 0,把 NNN 拆成各个位数相加,如将 123 拆成 100 + 20 + 3,计算过程同时求余即可。
AC代码
方法一
方法二
复杂度分析
计算过程需要用到 NNN 中的各个位数,则复杂度为 NNN 的长度,即O(∣N∣)O(|N|)O(∣N∣)。