1922. 统计好数字的数目 - 力扣(Leetcode)
题解
思路一:快速幂
#define MOD 1000000007
long long power(int n, long long times)
{
if(times == 1) return n;
if(times == 0) return 1;
long long next = power(n, times / 2);
return next * next * power(n, times % 2) % MOD;
}
int countGoodNumbers(long long n) {
long long four_times = n / 2;
long long five_times = four_times + n % 2;
return (power(4, four_times) * power(5, five_times)) % MOD;
}
思路二:暴力打表
#define MOD 1000000007
int countGoodNumbers(long long n) {
int mark = n % 2;
long long ans = 1;
while (n - pow(10, 14) > 0) {
n -= pow(10, 14);
ans = (ans * 918742959) % MOD;
}
while (n - pow(10, 13) > 0) {
n -= pow(10, 13);
ans = (ans * 567839794) % MOD;
}
while (n - pow(10, 12) > 0) {
n -= pow(10, 12);
ans = (ans * 857412984) % MOD;
}
while (n - pow(10, 11) > 0) {
n -= pow(10, 11);
ans = (ans * 454060842) % MOD;
}
while (n - pow(10, 10) > 0) {
n -= pow(10, 10);
ans = (ans * 176203868) % MOD;
}
while (n - pow(10, 9) > 0) {
n -= pow(10, 9);
ans = (ans * 142875001) % MOD;
}
while (n - pow(10, 8) > 0) {
n -= pow(10, 8);
ans = (ans * 468083689) % MOD;
}
while (n - pow(10, 7) > 0) {
n -= pow(10, 7);
ans = (ans * 924188482) % MOD;
}
while (n - pow(10, 6) > 0) {
n -= pow(10, 6);
ans = (ans * 171395901) % MOD;
}
while (n - pow(10, 5) > 0) {
n -= pow(10, 5);
ans = (ans * 86331955) % MOD;
}
while (n - pow(10, 4) > 0) {
n -= pow(10, 4);
ans = (ans * 325891746) % MOD;
}
while (n - pow(10, 3) > 0) {
n -= pow(10, 3);
ans = (ans * 36020987) % MOD;
}
while (n - pow(10, 2) > 0) {
n -= pow(10, 2);
ans = (ans * 564490093) % MOD;
}
while (n - pow(10, 1) > 0) {
n -= pow(10, 1);
ans = (ans * 3200000) % MOD;
}
while ((n -= 2) >= 0) {
ans *= 20;
ans %= MOD;
}
if (mark)
return (ans * 5) % MOD;
return ans;
}
标签:10,题解,ans,while,long,1922,pow,LeetCode,MOD
From: https://www.cnblogs.com/fjnhyzCYL/p/16895943.html