解题思路

这是一个关于幂运算的计数问题。通过分析可以将问题分为两种情况：

  1. 当a=c时：

    • 当 时，式子个数为
    • 当 时（），式子个数为
    • 合计：

  2. 当a≠c时：

    • 可转化为
    • 需要遍历i，且满足
    • 通过最大公约数来优化计算

代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

long long solve(int n) {
    // 计算a=c的情况
    long long result = (2LL * n * n - n) % MOD;
    
    unordered_set<int> seen;
    for (int i = 2; i * i <= n; i++) {
        if (seen.count(i)) continue;
        
        // 计算i的幂次
        int base = i, pow = 0;
        while (base <= n) {
            seen.insert(base);
            pow++;
            base *= i;
        }
        
        // 计算不同幂的组合
        for (int x = 1; x <= pow; x++) {
            for (int y = x + 1; y <= pow; y++) {
                result = (result + (n / (y / gcd(x, y))) * 2) % MOD;
            }
        }
    }
    
    return result;
}

int main() {
    int n;
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}

import java.util.*;

public class Main {
    static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            System.out.println(solve(n));
        }
    }

    static long solve(int n) {
        // 计算a=c的情况
        long result = (2L * n * n - n) % MOD;
        
        Set<Integer> seen = new HashSet<>();
        for (int i = 2; i * i <= n; i++) {
            if (seen.contains(i)) continue;
            
            // 计算i的幂次
            int base = i, pow = 0;
            while (base <= n) {
                seen.add(base);
                pow++;
                base *= i;
            }
            
            // 计算不同幂的组合
            for (int x = 1; x <= pow; x++) {
                for (int y = x + 1; y <= pow; y++) {
                    result = (result + (n / (y / gcd(x, y))) * 2) % MOD;
                }
            }
        }
        
        return result;
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

def solve(n):
    MOD = 1000000007
    # 计算a=c的情况
    result = (2 * n * n - n) % MOD
    
    seen = set()
    i = 2
    while i * i <= n:
        if i in seen:
            i += 1
            continue
            
        # 计算i的幂次
        base, pow_count = i, 0
        while base <= n:
            seen.add(base)
            pow_count += 1
            base *= i
            
        # 计算不同幂的组合
        for x in range(1, pow_count + 1):
            for y in range(x + 1, pow_count + 1):
                result = (result + (n // (y // gcd(x, y))) * 2) % MOD
                
        i += 1
    return result

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

if __name__ == "__main__":
    n = int(input())
    print(solve(n))

算法及复杂度

  • 算法：数学 + 最大公约数优化
  • 时间复杂度：
  • 空间复杂度：