C++ 破解“好数字”个数难题：巧用奇偶位选择与快速幂算法

```cpp #include <iostream> using namespace std; const int MOD = 1e9 + 7; long long fast_pow(long long base, long long exp) { long long res = 1; while (exp > 0) { if (exp % 2 == 1) { res = (res * base) % MOD; } base = (base * base) % MOD; exp /= 2; } return res; } int countGoodNumbers(long long n) { long long even_pos = (n + 1) / 2; // 偶数位的个数 long long odd_pos = n / 2; // 奇数位的个数 long long even_choices = 5; // 偶数位可选数字：0,2,4,6,8 long long odd_choices = 4; // 奇数位可选数字：2,3,5,7 long long res = (fast_pow(even_choices, even_pos) * fast_pow(odd_choices, odd_pos)) % MOD; return res; } int main() { long long n; cin >> n; cout << countGoodNumbers(n) << endl; return 0; } ``` 代码解释： 1. 偶数位（下标0,2,4...）必须为偶数（0,2,4,6,8），共5种选择 2. 奇数位（下标1,3,5...）必须为质数（2,3,5,7），共4种选择 3. 总可能性数为5^even_pos * 4^odd_pos，其中even_pos和odd_pos分别表示偶数位和奇数位的数量 4. 使用快速幂算法计算大数幂次，避免超时 5. 结果对1e9+7取模 三条额外需要注意的逻辑点： - 偶数位和奇数位的数量计算需要考虑n的奇偶性 - 快速幂算法的时间复杂度是O(log n)，适合处理大指数 - 模运算要在每次乘法后进行，防止中间结果溢出 ######[AI写代码神器 | 457点数解答 | 2025-07-21 17:46:17]