当前位置: 代码迷 >> 综合 >> BestCoder Round #80 Segment
  详细解决方案

BestCoder Round #80 Segment

热度:28   发布时间:2023-12-06 03:36:27.0

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5666

让我们先看看这道题目的官方题解

1002

考虑一条以(0,0)(0,0)为起点,(x,y)(x,y)为终点的线段上格点的个数(不包含端点时),一定是gcd(x,y)-1gcd(x,y)?1,这个很显然吧.

然后整个网格图范围内的格点数目是\frac {q*(q-1)} 2?2??q?(q?1)??.

所以答案就是\frac {q*(q-1)} 2 -?2??q?(q?1)??? 所有线段上的格点的个数.

因为gcd(a,b)=gcd(a,b-a)\ (b>a)gcd(a,b)=gcd(a,b?a) (b>a),所以gcd(x,y)=gcd(x,p-x)=gcd(x,p)gcd(x,y)=gcd(x,p?x)=gcd(x,p),p是质数,所以gcd(x,y)=1gcd(x,y)=1,所以线段上都没有格点,所以答案就是\frac {q*(q-1)} 2?2??q?(q?1)??.


这就是官方的解释,其实在这个公式推导上并没有什么问题,很容易想到的是在这个三角形内部的点,但是这道题目的一个关键还在这个大数据,凭着找到了一组大数据的质数,小编我在组内hack了7个人,直接加了700分(这波简直不亏),因为long long的数据范围是到2^63,大概就是10^18次方,如果不用大数处理或者不用快速幂类的方法肯定会炸long long,这里小编就介绍一下快速幂类的方法。

我们要求的是q*(q-1)/2这个数,相当于我们要求(q-1)/2个q的和(这里还需要判断一下奇偶),仔细回想一下快速幂的用法,快速幂是快速处理一个数的n次幂的,也就是n个数的积,如果我们这里把这个积改成和,就和快速幂一样能够快速解决这个问题,因为快速幂的每一步都会取模,所以也不用担心会出现炸long long的情况。

#include <cstdio>
#define LL __int64
LL fast_mul(LL a, LL b, LL p)
{LL ret = 0;  while(b) {  if(b & 1) ret = (ret + a) % p;  a = (a + a) % p;b >>= 1;  }  return ret % p;  
}  
int main()
{int t;LL x,y,ans;scanf("%d",&t);while (t--){scanf("%I64d%I64d",&x,&y);if ((x-2)%2==0) ans = fast_mul((x-2)/2,x-1,y);else ans = fast_mul((x-2),(x-1)/2,y);printf("%I64d\n",ans);}
}


  相关解决方案