【bzoj2659】算不出的算式

  • 数形结合好题一道

刚看到这道题的时候，我是懵逼的，这式子根本无法下手啊

难道是真· 欧几里得？或者维护数值之类的奇淫技巧？

然后看到了题解，真是妙啊，居然是数形结合

注意到 $\frac{p}{q}$ 可是看成一条直线的斜率，那么 $\sum_{k=1}^{\frac{p-1}{2}}[\frac{kp}{q}]$ 就可以看成直线 $y=\frac{p}{q}x与x=\frac{p-1}{2}$ 围成的三角形中整数点的数量

所以 $ans=\frac{(p-1)(q-1)}{4}$

注意当 $p=q$ 时，直线上的点应该算两遍，$ans=\frac{p^2-1}{4}$

真是妙啊，蒟蒻完全没有想到应该这样做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
typedef long long ll;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	int q=read(),p=read();
	if(p==q)  printf("%lld\n",((ll)p*p-1)>>2);
	else printf("%lld\n",(ll)(p-1)*(q-1)>>2);
	return 0;
}

本文标题:【bzoj2659】算不出的算式

文章作者:chty

发布时间:2017年03月16日 - 16时38分

最后更新:2018年03月02日 - 17时25分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,