Link Sub: http://www.spoj.com/PTIT/problems/PTIT017A/
Người Gửi: Sai
- Problem:
Cho các số nguyên A, B, K. Nhiệm vụ của bạn là hãy đếm xem trong đoạn [A, B] có bao nhiêu số có đúng K ước số nguyên tố. Ví dụ số 12 có 2 ước số nguyên tố (2 và 3), số 550 có 3 ước số nguyên tố (2, 5, và 11), trong khi số 17 chỉ có 1 ước số nguyên tố duy nhất là chính nó.
Input
Dòng đầu tiên là số lượng bộ test T (T ≤ 100).
Mỗi test gồm 3 số nguyên A, B, K (2 ≤ A, B ≤ 107, 1 ≤ K ≤ 109)
Output
Với mỗi test in ra chữ “Case” kèm theo số thứ tự bộ test và đáp án tìm được (theo mẫu như trong ví dụ).
Example:
Với mỗi test in ra chữ “Case” kèm theo số thứ tự bộ test và đáp án tìm được (theo mẫu như trong ví dụ).
Input
5
5 15 2
2 10 1
24 42 3
1000000 1000000 1
1000000 1000000 2
Output:
Case #1: 5
Case #2: 7
Case #3: 2
Case #4: 0
Case #5: 1
- Solution:
Chú Ý: Code dưới đây sub bằng C++6.3: time limit, C++4.3.2: 0.65s ???
Ý tưởng:
- Sàng nguyên tố trong khoảng từ 1->10^7. (arr[])
- Mỗi nguyên tố xét duyệt các bội của nó. Bội của các số nguyên tố sẽ có ước là số nguyên tố đó -> dùng mảng đánh dấu (arr2[]) ghi nhận lại số ước số nguyên tố của số đó.
VD: 1->5 -> (arr[1]=0, arr[2]=1, arr[3]=1, arr[4]=0, arr[5]=1);
-> v[]={2, 3, 5} là các số nguyên tố.
với v[0]=2 -> arr2[2]= 1, arr2[3]= 0, arr2[4]= 1, arr2[5]= 0;
với v[1]=3 -> arr2[2]= 1, arr2[3]= 1, arr2[4]= 1, arr2[5]= 0;
với v[3]=5 -> arr2[2]= 1, arr2[3]= 1, arr2[4]= 1, arr2[5]= 1;
-> Vậy arr2[i] tương đương với số ước nguyên tố của i;
- Code:
C++:
https://ideone.com/HyEtOE
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <vector>
#define MAX 10000000
using namespace std;
long arr[10000007];
long arr2[10000007];
void init ()
{
for (long i=1; i<=MAX; i++)
{
arr[i]=1;
arr2[i]=0;
}
arr[1]=0;
}
void sangNT ()
{
for (long i=2; i<=sqrt(MAX); i++)
{
if (arr[i]==1)
{
for (long j=2; j<=MAX/i; j++)
{
arr[j*i]=0;
}
}
}
}
int main ()
{
init ();
sangNT ();
vector <long> v;
for (long i=1; i<=MAX; i++)
{
if (arr[i]==1) v.push_back(i);
}
for (long i=0; i<v.size(); i++)
{
for (long j=1; j<=MAX/v[i]; j++)
{
arr2[v[i]*j]++;
}
}
int t;
cin>>t;
for (int k=1; k<=t; k++)
{
long A, B, K, count=0;
cin>>A>>B>>K;
for (long i=A; i<=B; i++)
{
if (arr2[i]==K) count++;
}
printf ("Case #%d: %ld\n", k, count);
}
return 0;
}