MYF

HDU 5750 Dertouzos

Posted on | In | | Visitors

题目链接

HDU 5750

题目类型：模拟 ＋ 筛法

题目分析

题目大意

给出一个n，一个d，找出小于n且最大因子为d的数的数量

解析

当d为素数时，显然只能用比d小且和d相乘小于n的素数。当d为合数时，要先找出来d中最小的质因子，该质因子可以被小于等于他的替换，也就是说，对于一个合数来讲，能组成的数字为小于等于其最小质因子且相乘之后小于n的素数。

所以我们一开始筛素数表的时候，就把每个数字的最小质因子筛出来，存在fac[]数组中。计算结果时，首先可以确定一个事情，最多只能有num[min((n-1)/d, fac[d])]个情况，其中(n-1)/d是当n不足够大的时候，d能乘以(n-1)/d以内的素数，所以共有num[(n-1)/d]种情况，当n足够大，大于fac[d]*fac[d]的时候，只能取所有小于等于fac[d]的素数了，这种情况共有num[fac[d]]个情况。

有一种特殊情况，当d大于我们的阈值时，要怎么处理？显然，上面的分析是无法处理d大于我们阈值的情况的，所以对于这些数字，我们可以先假定它是合数，那么必然在我们阈值范围内，存在他的一个质因子。当我们找到他的最小质因子的时候，直接返回num[fac[d]]即可，因为是遍历出来的，所以当前的这个值，及之前的值是可取的。若跑完我们范围内的素数，仍然没有找到的话，说明他是素数，直接认为(n-1)/d范围内的所有素数都可以作为结果即可，也就是num[(n-1)/d]。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define pb push_back
#define mp make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : "<<x<<" "<<y<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn=10000010+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int prime[maxn],fac[maxn],num[maxn],pcnt;
void Init_Prime(){
    pcnt=0;
    for (int i=2; i<maxn; i++) {
        if (!fac[i]) {
            fac[i]=i;
            num[i]=1;
            prime[pcnt++]=i;
        }
        for (int j=0; j<pcnt&&i*prime[j]<maxn; j++) {
            fac[i*prime[j]]=prime[j];
            if (!i%prime[j]) break;
        }
        num[i]+=num[i-1];
    }
}
int solve(int n,int d){
    int tmp = n / d;
    if (d<maxn) {
        return num[min(tmp, fac[d])];
    }
    for (int i=0; prime[i]<tmp; i++) {
        if (d % prime[i]==0) {
            return i+1;
        }
    }
    return num[tmp];
}
int main(){
    Init_Prime();
    int t,n,d;
    scanf("%d",&t);
    while (t--) {
        scanf("%d%d",&n,&d);
        cout<<solve(n-1,d)<<endl;
    }
    return 0;
}