hdu5666 (数学水题）

古城微笑少年丶 2022-08-21 06:56 240阅读 0赞

![Image 1][]

标准解释：

考虑一条以(0,0)(0,0)为起点,(x,y)(x,y)为终点的线段上格点的个数（不包含端点时）,

一定是gcd(x,y)-1gcd(x,y)−1,这个很显然吧.

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

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

因为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-1）∗(q−2)​​.

比赛的时候我是通过画图然后递推退出来这个结果的。

接下来就是求（(q-1)*(q-2)/2) % p 了，并且，这个都不是质数。

有套路的，看代码。

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  6. using namespace std;
  8. #define LL long long
  9. #define INF 0x3f3f3f3f3
  11. LL multiply(LL n , LL m , LL mod)
  12. {
  13.     LL sum = 0 ; 
  14.     while(m)
  15.     {
  16.         if(m&1)
  17.         {
  18.             sum += n ; 
  19.             sum %= mod ; 
  20.         }
  21.         m >>= 1 ; 
  22.         n *= 2 ; 
  23.         n %= mod ; 
  24.     }
  25.     return sum ; 
  26. }
  28. int main()
  29. {
  30.     int t ; 
  31.     LL q,p ; 
  32.     scanf("%d",&t);
  33.     while(t--)
  34.     {
  35.         scanf("%I64d%I64d",&q,&p)  ;
  36.         printf("%I64d\n",multiply((q-1),(q-2),2*p)/2) ; 
  37.     }
  38.     return 0 ; 
  39. }

[Image 1]:

发表评论

表情：
评论列表 （有 0 条评论，240人围观）

还没有评论，来说两句吧...

相关阅读