[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 A: qwb与支教 [容斥]【数学】

Tabris

CSDN数学套题

发布于：2017年6月3日

次浏览

[原创]2017 年第 0 届浙江工业大学之江学院程序设计竞赛决赛 A: qwb 与支教 [容斥]【数学】

2017-06-03 01:36:38 Tabris_ 阅读数：1047

博客爬取于 2020-06-14 22:40:23
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849484

题目链接：http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=0

————————————————————————————————————————
Problem A: qwb 与支教
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1457 Solved: 268
[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≤107,1≤N≤1017）。

Output
对于每个测试例，输出第 N 名学生所报的数字，每个报数占一行。
Sample Input
2 3 5 2
6 2 4 10000
Sample Output
7
19999

————————————————————————————————————————

学过容斥的人应该都会，不会的话坐下 hdu 1796

附本题代码
——————————————————————————

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

# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;
/**************************************/
LL lcm(LL a,LL b){
    return a/__gcd(a,b)*b;
}
LL x,y,z,N;
LL cal(LL k){
    LL sum = k;
    sum-=k/x+k/y+k/z;
    sum+=k/lcm(x,y)+k/lcm(y,z)+k/lcm(x,z);
    sum-=k/lcm(x,lcm(y,z));  //baojingdu
//    cout<<"sum = "<<sum<<endl;
    return sum;
}

int main(){
    while(~scanf("%lld%lld%lld%lld",&x,&y,&z,&N)){
        LL l=1,r=(~(1ll<<63))>>1,mid,ans=1;
        while(l<=r){
            mid = r+l >> 1;
            if(cal(mid)>=N) ans=mid,r=mid-1;
            else l=mid+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

本页文档最后更新于：2021年5月16日

CSDN

数学