BZOJ2659: [Beijing wc]算不出的算式

2659: [Beijing wc]算不出的算式

Time Limit: 3 SecMemory Limit: 128 MB

Submit: 1489Solved: 891

[Submit][Status][Discuss]

Description

算不出的算式

背景：

曾经有一个老掉牙的游戏放在我面前，我没有珍惜。直到这个游戏停产才追悔莫及。人世间最痛苦的事情莫过于此，如果上天给我一个再玩一次的机会，我一定要，通关！

题目描述：

如果你真的很想玩这个游戏，那么就先看看我的题目吧，搞不定这些的话是没办法通关的哟。第一关其实很简单，只有一个关闭的有密码锁的大门。这大门上写着一个奇怪的算式，估计是要你利用它算出密码来开门吧（果然是老掉牙的情节）。

传说中这个式子中的p和q是两个奇质数，等号右边算出来应该就是密码了吧，你是真的算不出来么？

Input

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

Output

一个数,表示算式结果。

Sample Input

5 7

Sample Output

6

HINT

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

Source

【题解】

数形结合/打表

静待我校没停课学了半年高二差两名进队dalao给证明。。。

tips:3min50s过后他证出来了。。。说是用什么高斯互反律。。。

打表大法好

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #define min(a, b) ((a) < (b) ? (a) : (b)) 9 #define max(a, b) ((a) > (b) ? (a) : (b))10 #define abs(a) ((a) < 0 ? (-1 * (a)) : (a))11 inline void swap(long long &a, long long &b)12 {13long long tmp = a;a = b;b = tmp;14 }15 inline void read(long long &x)16 {17x = 0;char ch = getchar(), c = ch;18while(ch < '0' || ch > '9') c = ch, ch = getchar();19while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();20if(c == '-') x = -x;21 }22 23 const long long INF = 0x3f3f3f3f;24 25 long long p,q;26 27 int main()28 {29read(p), read(q);30if(p == q) printf("%lld", (p - 1)*(q + 1) >> 2);31else printf("%lld", (p - 1)*(q - 1) >> 2);32return 0;33 }

BZOJ2659