反素数求解

反素数指约数个数多于所有小于它的正整数的数字。以下算法通过深度优先搜索枚举质因子指数组合，寻找不超过给定值n的最大反素数。

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const vector<int> primes = {2,3,5,7,11,13,17,19,23,29};
ll max_value, result, max_factors;

void find_antiprime(int pos, ll factor_count, ll current) {
    if(pos >= primes.size()) return;
    
    if(factor_count > max_factors || 
      (factor_count == max_factors && current < result)) {
        result = current;
        max_factors = factor_count;
    }
    
    for(int exp = 1; exp <= 30; ++exp) {
        if(primes[pos] * current > max_value) break;
        current *= primes[pos];
        find_antiprime(pos + 1, factor_count * (exp + 1), current);
    }
}

int main() {
    cin >> max_value;
    find_antiprime(0, 1, 1);
    cout << result;
    return 0;
}

最大公约数

互质与欧拉函数

欧拉函数φ(n)表示小于n的正整数中与n互质的数的数量。以下实现使用线性筛法高效计算欧拉函数：

void compute_euler(int n) {
    vector<bool> is_prime(n+1, true);
    vector<int> primes;
    vector<int> phi(n+1);

    for(int i = 2; i <= n; ++i) {
        if(is_prime[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for(int p : primes) {
            if(i * p > n) break;
            is_prime[i * p] = false;
            
            if(i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            } else {
                phi[i * p] = phi[i] * (p - 1);
            }
        }
    }
}

坐标系可见点问题

在第一象限内，若点(x,y)与原点(0,0)的连线上无其他整数点，则该点可见。给定N，求满足0≤x,y≤N的可见点数量（不含原点）。

#include <iostream>
#include <vector>
using namespace std;

vector<int> euler_values(int n) {
    vector<bool> composite(n+1, false);
    vector<int> primes;
    vector<int> phi(n+1);
    phi[1] = 1;

    for(int i = 2; i <= n; ++i) {
        if(!composite[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for(int p : primes) {
            if(i * p > n) break;
            composite[i * p] = true;
            phi[i * p] = (i % p == 0) ? 
                phi[i] * p : phi[i] * (p - 1);
            if(i % p == 0) break;
        }
    }
    return phi;
}

int main() {
    int test_count;
    cin >> test_count;
    
    for(int i = 1; i <= test_count; ++i) {
        int N;
        cin >> N;
        auto phi = euler_values(N);
        
        long total = 0;
        for(int j = 2; j <= N; ++j) {
            total += 2 * phi[j];
        }
        
        cout << i << " " << N << " " << total + 3 << "\n";
    }
    return 0;
}