兰州做网站的公司/百度怎么转人工客服

链接

D
Luogu P4296

题目描述

给定n，求出所有正整数x，满足小于n，且x^2(%n)=1
将满足的x按从小到大的顺序依次换行输出

思路

$$x^2\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)$$
$$(x+1)(x-1)=kn$$
$$(x+1)=k_1{n}_1(k_1|k,n_1|n）$$
$$(x-1)=k_2{n}_2（k_2|k,n_2|n）$$
那么很显然因为$k_1{n}_1⩽n$，所以$k_1⩽\frac{n}{n_1}$
那肯定不能让$n_1$太小，要不然就T飞了
又可以发现$n_1{n}_2=n$
那么$n_2=\frac{n}{n_1}$
那是不是只需要枚举一个大于$\sqrt{n}$的$n$的约数，然后再求$n_2$，验证求出的x是否为$n_2$的倍数就好了

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long longusing namespace std;ll n, cnt, t;
ll ans[500005], an[500005];bool check(ll a)
{for(int j = 0; j * a <= n; ++j){ll a2 = n / a;if((j * a - 2) % a2 == 0) ans[++cnt] = j * a - 1;if((j * a + 2) % a2 == 0)ans[++cnt] = j * a + 1;}	
}int main()
{scanf("%lld", &n);if(n == 1) {printf("None\n");return 0;}for(ll i = 1; i <= floor(sqrt(n)); ++i) {if(n % i == 0 && i * i != n) an[++t] = n / i;else if(i * i == n){an[++t] = i;break;}}	for(int i = 1; i <= t; ++i) check(an[i]);sort(ans + 1, ans + cnt + 1);int m = unique(ans + 1, ans + cnt + 1) - ans - 1;int l = 1, r = m;while(ans[l] < 0) l++;while(ans[r] >= n) r--;if(r - l + 1 == 0) {printf("None\n");return 0;}for(int i = l; i <= r; ++i)printf("%lld\n", ans[i]);return 0;
}