hdu3388容斥还有二分

Posted by Cww97 on 2016-08-13

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52199326
http://acm.hdu.edu.cn/showproblem.php?pid=3388

题意:有三个正整数m, n, k, 求与m和n都互质第k个正整数(按从小到大排列)。

一点废话:
讲m,n所以质因子提出,去重排序
求出mid中含这些因子的数的个数=ans,然后mid-ans就是第k个与m,n互质的数
都用mid了,,,二分之
下面的问题还剩怎么求ans,
容斥了,对于素数p[i],1到n里面含有这个因子的数的个数为n/p[i]
很多个素数会有重复的,那再减n/(p[i]p[j])
这减的里面还有重复的,再加n/(p[u]
p[j]p[k])
……
容斥容斥容斥:
拿质因子2,3,5举例
ans = (n/2+n/3+n/5)-(n/(2
3)+n/(25)+n/(35))+(n/(235))
容斥拿dfs写,奇数个ans+=,偶数个-=

真-废话
素数表打到sqrt(n)就行了
话说我忘了考虑一个大素数的情况,少了这两行
if (m > 1) fac[++F] = m;
if (m != n && n > 1) fac[++F] = n;
WA了一晚上,这里写图片描述
(不是废话) 感谢WY,感谢WY,感谢WY,这里写图片描述

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll N=100007;
ll p[N],P,fac[N],F,ans;
bool isPrime[N];

void getPrime(){
P=0;
memset(isPrime,1,sizeof(isPrime));
for (ll i=2;i<N;i++){
if(isPrime[i]) p[++P] = i;
for (int j=1;j<=P&&p[j]*i<N;j++){
isPrime[i*p[j]] = 0;
if (i%p[j]==0) break;
}
}
}

void dfs(ll s,ll start,ll cnt,ll mid){
if (cnt&1) ans += mid/s;
else ans -= mid/s;
for (ll i=start+1;i<=F;i++){
dfs(s*fac[i],i,cnt+1,mid);
}
}

int main(){
//freopen("fuck.in","r",stdin);
int T; scanf("%d",&T);
ll n,m,k;
getPrime();
for (int cas=1;cas<=T;cas++){
scanf("%I64d%I64d%I64d",&n,&m,&k);
if (n==1&&m==1){
printf("Case %d: %I64d\n",cas,k);
continue;
}
F=0;
for (ll i=1;i<=P&&p[i]<=max(m,n);i++){
if (n%p[i]==0||m%p[i]==0){
while (n%p[i]==0) n/=p[i];
while (m%p[i]==0) m/=p[i];
fac[++F]=p[i];
}
}
if (m > 1) fac[++F] = m;
if (m != n && n > 1) fac[++F] = n;

ll l=0,r=INF;
for (;l<r;){
ll mid = (l+r)>>1;
ans = 0;
for (ll i=1;i<=F;i++)dfs(fac[i],i,1,mid);
//printf("check(%I64d)=%I64d\n",mid,mid-ans);
if (mid-ans < k) l = mid+1;
else r = mid;
}
printf("Case %d: %I64d\n",cas,l);
}
return 0;
}