UVa 12865 - Volume Control

contents

1. 1. Problem
2. 2. Sample Input
3. 3. Sample Output
4. 4. Solution

Problem

1, 2, 4, 7, 10, 15, 19, 26, 31, 37, 43, 54, 60, 73

A027384 Number of distinct products ij with 0 <= i, j <= n.

詢問 0 到 N 的連續整數，任兩個挑出來相乘，有多少不同的整數。

Sample Input

2
3
4

Sample Output

7
10

Solution

聽說當下比賽很多人直接本地建表，不過這一題還真的不知道該怎麼解比較好。

用了窮舉的方式，加入第 i 個整數，將與 0 ~ i 相乘，這時候增加多少不同整數？

1. 找到 i * j == p * q 其中滿足 p, q < i，要忽略所有可能的 j，剩餘的結果就是增加的數量。
2. 假設 i = a * b, p = a * ?1, q = b * ?2。
3. 得到 j = ?1 * ?2、?2 < a, ?1 < b。

用嚴格增加的趨勢，依序窮舉 i 的因數 a (小到大)，?2 可以帶入的數字會遞增，而 ?1 會遞減，而中間會有一段重複的窮舉，只考慮 ?2 進行遞增即可。將不好的 j 給篩掉。

#include <stdio.h> 
#include <set>
#include <math.h>
#include <vector>
using namespace std;

int main() {
    int ret[65536] = {1}, sum = 1;
    int nop[32767] = {}, cases = 0;
    for (int i = 1; i <= 30000; i++) {
        vector<int> f;
        int first_prime;
        for (int j = 2; j * j <= i; j++) {
            if (i%j == 0) {
                f.push_back(j);
            }
        }
        // i * j == p * q (p, q < i)
        // i = a * b, p = a * ?1, q = b * ?2
        // j = ?1 * ?2
        cases++;
        first_prime = f.size() ? f[0] : i;
        for (int j = 0, q1, q2 = 2; j < f.size(); j++) { // f[j] x (i / f[j])
            for (; q2 < f[j]; q2++) { // ?2 < a, ?1 < b
                for (q1 = i/ f[j] - 1; q1 >= 1; q1--)
                    nop[q1 * q2] = cases;
            }
        }
        for (int j = i / first_prime; j <= i; j++)
            sum += nop[j] != cases;
        ret[i] = sum;
    }
    int testcase, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        printf("%d\n", ret[n]);
    }
    return 0;
}