BZOJ2659: [Beijing wc2012]算不出的算式(数学)

2018-07-03 01:01:25来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 1575  Solved: 939
[Submit][Status][Discuss]

Description

算不出的算式
背景:
曾经有一个老掉牙的游戏放在我面前,我没有珍惜。直到这个游戏停产才追悔莫及。人世间最痛苦的事情莫过于此,如果上天给我一个再玩一次的机会,我一定要,通关!
题目描述:
如果你真的很想玩这个游戏,那么就先看看我的题目吧,搞不定这些的话是没办法通关的哟。第一关其实很简单,只有一个关闭的有密码锁的大门。这大门上写着一个奇怪的算式,估计是要你利用它算出密码来开门吧(果然是老掉牙的情节)。
传说中这个式子中的p和q是两个奇质数,等号右边算出来应该就是密码了吧,你是真的算不出来么?

Input

只有一行,两个奇质数,分别表示p,q。

 

Output

一个数,表示算式结果。

 

Sample Input

5 7

Sample Output

6

HINT

 

HINT:p,q在32位整型范围内。

 

Source

An Introduction to the Theory of Numbers第6版定理100

 
 
太难了qwq。。根本想不到啊qwq。
那前面那个式子来说,我们可以把它看做是$y = k \frac{q}{p}$这条直线某点下方的整点数,
我们要取遍$1<=k<=\frac{p - 1}{2} $
同时不难看出后面的式子是它的反函数
于是他们组成了一个矩阵,我们要求的就是矩阵的面积
然后特判一下相等的情况(也就是点落在直线上)
 
#include<cstdio>
using namespace std;
int main() {
    long long  p, q;
    scanf("%lld %lld", &p, &q);
    printf("%lld", (p / 2) * (q / 2) + ((p == q) ? (p / 2) : 0));
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:用java集合模拟登录和注册功能

下一篇:vs2017中的scanf_s