【HDU5750 BestCoder Round 84D】【数学贪心复杂度计算】Dertouzos 范围有多少数的最大真约数为d

本文主要是介绍【HDU5750 BestCoder Round 84D】【数学贪心复杂度计算】Dertouzos 范围有多少数的最大真约数为d，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Dertouzos

Accepts: 76

Submissions: 1357

Time Limit: 7000/3500 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

问题描述

正整数 $x$ 称为 $n$ 的positive proper divisor, 当且仅当 $x ∣ n$ 并且 $\le x < n$ . 例如, 1, 2, 和3是6的positive proper divisor, 但是6不是.Peter给你两个正整数 $n$ 和 $d$ . 他想要知道有多少小于 $n$ 的整数, 满足他们的最大positive proper divisor恰好是 $d$ .

输入描述

输入包含多组数据, 第一行包含一个整数 $T$   $\le T \le 10^6)$ 表示测试数据组数. 对于每组数据:第一行包含两个整数 $n$ 和 $d$   $\le n, d \le 10^9)$ .

输出描述

对于每组数据, 输出一个整数.

输入样例

输出样例

#include<stdio.h>
#include<algorithm>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 0, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
const int TOP = 4e5 + 10;
bool e[TOP];
int p[TOP];
int pnum;
int sum[TOP];
void prime()
{e[0] = e[1] = 1; pnum = 0;for (int i = 2; i<TOP; i++){sum[i] += sum[i - 1];if (e[i] == 0){p[++pnum] = i;++sum[i];}for (int j = 1; j <= pnum&&p[j] * i<TOP; j++){e[p[j] * i] = 1;if (i%p[j] == 0)break;}}
}
int n, d;
int main()
{prime();scanf("%d", &casenum);for (casei = 1; casei <= casenum; ++casei){scanf("%d%d", &n, &d);int top = min(d, (n - 1) / d);int topp = min(top, (int)sqrt(d));for (int i = 1; p[i] <= topp; ++i){if (d%p[i] == 0){gmin(top, p[i]);break;}}printf("%d\n", sum[top]);}return 0;
}
/*
【trick&&吐槽】
这道题自信满满地写完，结果最后FST (TLE)
本来可以红名的，结果跌了100分。
比赛的时候，一定要好好算复杂度啊。能压则压，这场比赛的C,D都死在了对复杂度的不严格要求上。衰= =#【题意】
我们称x为y的“最大真约数”，当且仅当x是y的约数，且x<y
现在给你两个正整数n个d，
问你，有多少个[1,n-1]范围的整数，满足——
该数的"最大真约数"恰好为d。【类型】
数学，贪心，复杂度计算。【分析】
首先，这些数必然是d的倍数，且是d的2~top倍。
且这个倍数，必须是素数，否则会产生比d更大的约数且这个倍数，最大只能为d，否则会使得最大因子不是d，
且这个倍数，不能超过(n-1)/d，因为数字范围有限制。
而min(d,(n-1)/d)是一个不超过3.2e4的数，我们预处理这里的素数个数即可。然而， 比赛的时候，这样交了一下，却收获一发WA，
我们进而发现，还应当有条件被满足——
因为d是这个数的最大约数。
所以，d的最大约数*该素数<=d一定要满足。
也就是说，该素数<=d的最小非1约数于是，该素数的范围是[ min(min(d,(n-1)/d), d的最小素因子)]
于是对于给定的d，我们去找其最小非1约数（显然该约数是个素数）。【时间复杂度&&优化】
O(T sqrt(d))
=>
O(T min(min(d,(n-1)/d), sqrt(d)))由单组最大3e4，缩小为1e3，就可以AC了*/

这篇关于【HDU5750 BestCoder Round 84D】【数学贪心复杂度计算】Dertouzos 范围有多少数的最大真约数为d的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！