浙江工业大学之江学院2017年第0届达内杯A题——qwb与支教

Problem A: qwb与支教

Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 1617   Solved: 332 [ Submit][ Status][ Web Board]

Description

qwb同时也是是之江学院的志愿者，暑期要前往周边地区支教，为了提高小学生的数学水平。她把小学生排成一排，从左至右从1开始依次往上报数。

玩完一轮后，他发现这个游戏太简单了。于是他选了3个不同的数x,y,z；从1依次往上开始报数，遇到x的倍数、y的倍数或z的倍数就跳过。如果x=2,y=3,z=5；第一名小学生报1，第2名得跳过2、3、4、5、6，报7；第3名得跳过8、9、10，报11。

那么问题来了，请你来计算，第N名学生报的数字是多少？

Input

多组测试数据，处理到文件结束。（测试数据数量<=8000）

每个测试例一行，每行有四个整数x,y,z,N。（ 2≤x,y,z≤10⁷,1≤N≤10¹⁷）。

Output

对于每个测试例，输出第N名学生所报的数字，每个报数占一行。

Sample Input

2 3 5 2 6 2 4 10000

Sample Output

7 19999

HINT

思路：一开始是找x,y,z的最小公倍数，报到最小公倍数加一的人就是一个循环节，之后的人每个报到的数就是之前循环节内的人报到的数+最小公倍数，不过这个方法并没有什么用，x,y,z取值范围太大了，万一超过1e18依旧要一个一个来找，所以我就A不了哈哈哈哈或，后来看了牛牪犇的题解才知道了利用容斥性，想找到第N个学生报到低级不容易，但是要找到第N个数之前有几个学生报到是不难，所以直接在【1，1e17】的区间里二分查找，因为学生编号是随着报到的数字递增的，所以可以用二分，注意了这里的N并不是一定会被报到的，比如x=3,y=4,Z=5.dp到mid等于9的时候9是3的倍数所以要继续dp，哎呀语文不好，还是直接看代码吧，需要注意的我会标注在代码里的。

代码：

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #define Max 1000000000000000000 typedef long long LL; LL gcd(LL a,LL b) //最大公约数，辗转相除法 { while(b!=0) { LL c=a%b; a=b; b=c; } return a; } LL lcm(LL a,LL b) // 最小公倍数，先求出a,b两个数的最大公约数， { LL gyz=gcd(a,b); //a,b两个数除以这个公约数的因子必定互质，再相乘两个因子与最大公约数得到最小公倍数 a=a/gyz; if(Max/a<b) //如果a和b的最小公倍数大于1e18就不用管了 return -1; return b*a; } int main() { LL x,y,z,N; while(scanf("%lld%lld%lld%lld",&x,&y,&z,&N)!=EOF) { LL l=0; LL r=Max; while(l+1<r) { LL m=(l+r)/2; LL _sum=m/x+m/y+m/z; _sum-=(m/lcm(x,y)+m/lcm(x,z)+m/lcm(y,z)); if(lcm(lcm(x,y),z)!=-1) _sum+=m/lcm(lcm(x,y),z); LL realsum=m-_sum; if(realsum<N) l=m; else//if(realsum>=N) 注意为何是>=，一定要二分到区间里只剩一个数才行。 r=m; } printf("%lld\n",r); } return 0; }