Fork me on GitHub

复赛冲刺Day1R1-Count题解

其实我感觉这道数论题还是挺简单的(虽然我不会)

这道数论题,我初看的时候是挺一脸懵逼的,然后据$wucstdio$大爷提供的思路,我们可以发现:
题意求的是$x$,$y$在$mod P$下的逆元,存在解的条件是$gcd(x,p)==1$,即x,p互质
所以由题解有
设 1 到 P − 1 中与 P 互质的数有 s 个,考虑这 s 个数与它
们的逆元组成的二元组,这些二元组一定符合条件,那么只要考
虑去重的问题

所以我们只需要知道从$1$到$n$中和$n$互质的数的个数
这个东西是什么呢?这个东西很明显是$phi$函数。
所以我们只需要求出$\phi(p)$,再加上$x^2\equiv1\pmod{p}$的数,最后除$2$就好了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

const int N = 1e7 + 10;

int n;
int tot , prime[N] , phi[N];
bool flag[N];

int main ( void ) {
scanf ( "%d" , &n );
flag[1] = 1;
phi[1] = 1;
for ( int i = 2 ; i <= n ; i++ ) {
if ( !flag[i] ) {
prime[++tot] = i;
phi[i] = i - 1;
}
for ( int j = 1 ; j <= tot && i * prime[j] <= n ; j++ ) {
flag[i * prime[j]] = 1;
if ( i % prime[j] == 0 ) {
phi[i * prime[j]] = phi[i] *prime[j];
break;
}
phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
long long ans = phi[n];
for ( long long i = 1 ; i <= n ; i++ )
if ( i * i % n == 1 )
ans++;
printf ( "%lld\n" , ( long long ) ( ans ) / 2 );
return 0;
}

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:复赛冲刺Day1R1-Count题解

文章作者:KRrrrrrrrr

发布时间:2018年11月01日 - 11:11

最后更新:2019年10月21日 - 11:10

原始链接:http://krrrr.xyz/2018/11/01/qbxtD1T1题解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。