職場の先輩がLargeの答えが合わないって言ってたので僕も解いてみた。
やり方は、例えばsampleの通り10-20の区間でP=3の場合、
- 3の倍数12,15,18を取り出す。この段階でグループ数は-3
- 取り出した数は全部独立してたので、新たにグループが1つできる。グループ数+1
- 5の倍数10,15,20を取り出す。この段階でグループ数は-2。(15は独立してないので取り出してもグループが減らない。だから-3じゃない。)
- 既にグループに入ってる15を含むので、新たにグループは出来ない(統合される)。グループ数+0
みたいな感じの操作を繰り返す。
どの数がどうグルーピングされるかは気にせず、数の増減だけ見る形で、実行時間は10秒くらい。
結果… ぜんぜん違うアルゴリズムの先輩と答えが一致して、GCJのシステムからは不正解いただきました。
あっれー？二人してなんか特殊なケースを見落としてるのかな。
[cpp]
#include <iostream>
#include <vector>
using namespace std;
static const int MAX_PRIME_NUMBER = 1000000;
int solve(vector<int>& primes, long long A, long long B, int P) {
int result = B – A + 1;
vector<bool> grouped(B – A + 1, false);
for (int i = 0; i < primes.size(); i++) {
int divisor = primes[i];
if (divisor >= P && divisor < B – A + 1) {
int remNum = 0;
int addNum = 0;
bool isInOtherGroup = false;
int first = (A % divisor == 0 ? 0 : (divisor – A % divisor));
for (int j = first; j < grouped.size(); j += divisor) {
if (!grouped[j]) {
remNum++;
grouped[j] = true;
} else {
isInOtherGroup = true;
}
}
if (!isInOtherGroup) {
addNum = 1;
}
result -= remNum – addNum;
}
}
return result;
}
int main() {
// prepare prime numbers
vector<int> primes;
vector<bool> temp(MAX_PRIME_NUMBER + 1, true);
for (int i = 2; i <= MAX_PRIME_NUMBER; i++) {
if (temp[i]) {
primes.push_back(i);
for (int j = i; j <= MAX_PRIME_NUMBER; j += i) {
temp[j] = false;
}
}
}
// read cases from standard input and print result to standard out
int N, P;
long long A, B;
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> A >> B >> P;
int result = solve(primes, A, B, P);
cout << "Case #" << i << ": " << result << endl;
}
return 0;
}
[/cpp]