N = (p1c1) * (p2c2) * ... * (pk^ck) 형태로 표현될 때 N2 = (p1(c12)) * (p2^ (c22)) * ... * (pk^ (ck*2)) 형태가 됩니다.

약수의 개수 f[N] = (c1+1)(c2+1)...(ck+1)

배수를 이용한 약수 개수 구하기

이 문제에서는 공식을 사용하지 않고, 약수를 구하는 대신 배수를 이용해 해결합니다.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 1000010;

int input_count;
int numbers[MAX_SIZE], frequency[MAX_SIZE], multiple_count[MAX_SIZE];

int main()
{
    scanf("%d", &input_count);

    for (int i = 0; i < input_count; i ++ )
    {
        scanf("%d", &numbers[i]);
        frequency[numbers[i]] ++ ;//빈도수 계산
    }

    for (int i = 1; i < MAX_SIZE; i ++ )
        for (int j = i; j < MAX_SIZE; j += i)//해당 수의 모든 배수에 빈도수 더하기
            multiple_count[j] += frequency[i];

    for (int i = 0; i < input_count; i ++ ) printf("%d\n", multiple_count[numbers[i]] - 1);

    return 0;
}

1/x + 1/y = 1/n을 만족하는 정수 x, y 쌍의 개수 구하기

https://www.acwing.com/problem/content/1296/ 최적화 결과 n!^2의 약수의 합으로 문제를 해결할 수 있습니다.

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int MAX_N = 1e6 + 10, MOD = 1e9 + 7;

int prime_numbers[MAX_N], prime_count;
bool is_composite[MAX_N];

void sieve(int limit)
{
    for (int i = 2; i <= limit; i ++ )
    {
        if (!is_composite[i]) prime_numbers[prime_count ++ ] = i;
        for (int j = 0; prime_numbers[j] * i <= limit; j ++ )
        {
            is_composite[prime_numbers[j] * i] = true;
            if (i % prime_numbers[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;

    sieve(n);

    int result = 1;
    for (int i = 0; i < prime_count; i ++ )
    {
        int p = prime_numbers[i];
        int exponent_sum = 0;
        for (int j = n; j; j /= p) exponent_sum += j / p;
        result = (LL)result * (2 * exponent_sum + 1) % MOD;
    }

    cout << result << endl;


    return 0;
}

반소수(anti-prime) 찾기

1. 최대 9개의 소인수를 가질 수 있습니다
2. 각 소인수의 지수는 최대 30입니다
3. 숫자가 증가할 때 모든 소인수의 지수는 반드시 감소합니다

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int prime_list[9]={2,3,5,7,11,13,17,19,23};

typedef long long LL;

int max_divisor_count;
int smallest_number;
int input_n;

void search(int current_index, int max_exponent, int current_number, int divisor_count)
{
    if(divisor_count > max_divisor_count || 
       (divisor_count == max_divisor_count && current_number < smallest_number))
    {
        max_divisor_count = divisor_count;
        smallest_number = current_number;
    }
    
    if(current_index == 9)return;
    
    for(int exponent = 1; exponent <= max_exponent; exponent++)
    {
        if((LL)current_number * prime_list[current_index] > input_n)
        break;
        
        current_number *= prime_list[current_index];
        search(current_index + 1, exponent, current_number, divisor_count * (exponent + 1));
    }
}

int main()
{
    cin >> input_n;
    
    search(0, 30, 1, 1);
    
    cout << smallest_number << endl;
    
    return 0;
}

x와 a의 최대공약수가 b이고, x와 c의 최소공배수가 d인 x 찾기

1. gcd(조건)를 만족하는지 확인
2. 두 자연수의 최대공약수와 최소공배수의 곱은 두 수의 곱과 같다는 성질을 이용
3. d를 소인수분해하여 가능한 모든 약수 후보 생성

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int LIMIT = 45000, MAX_FACTORS = 50;

int prime_numbers[LIMIT], prime_count;
bool is_composite[LIMIT];

PII prime_factors[MAX_FACTORS];
int factor_count;

int divisors[LIMIT], divisor_count;

void sieve(int limit)
{
    for (int i = 2; i <= limit; i ++ )
    {
        if (!is_composite[i]) prime_numbers[prime_count ++ ] = i;
        for (int j = 0; prime_numbers[j] <= limit / i; j ++ )
        {
            is_composite[prime_numbers[j] * i] = true;
            if (i % prime_numbers[j] == 0) break;
        }
    }
}

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

void generate_divisors(int position, int current_product)
{
    if (position > factor_count)
    {
        divisors[divisor_count ++ ] = current_product;
        return;
    }

    for (int exponent = 0; exponent <= prime_factors[position].second; exponent ++ )
    {
        generate_divisors(position + 1, current_product);
        current_product *= prime_factors[position].first;
    }
}

int main()
{
    sieve(LIMIT);

    int test_cases;
    scanf("%d", &test_cases);
    while (test_cases -- )
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);

        int lcm = d;
        factor_count = 0;
        for (int i = 0; prime_numbers[i] <= lcm / prime_numbers[i]; i ++ )
        {
            int p = prime_numbers[i];
            if (lcm % p == 0)
            {
                int exponent = 0;
                while (lcm % p == 0) exponent ++, lcm /= p;
                prime_factors[ ++ factor_count] = {p, exponent};
            }
        }
        if (lcm > 1) prime_factors[ ++ factor_count] = {lcm, 1};

        divisor_count = 0;
        generate_divisors(1, 1);

        int answer = 0;
        for (int i = 0; i < divisor_count; i ++ )
        {
            int candidate = divisors[i];
            if (gcd(candidate, a) == b && (LL)candidate * c / gcd(candidate, c) == d)
            {
                answer ++ ;
            }
        }

        printf("%d\n", answer);
    }

    return 0;
}