本文主要是介绍【模拟赛】【数论】2021.8.12.D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
- 题目描述
- 思路
- 代码
题目描述
给出n，求所有x，使得x小于n，且 x 2 % n = 1 x ^ 2\ \%\ n\ =\ 1 x2 % n = 1
将所有x从小到大输出
思路
x 2 % n = 1 x ^ 2\ \%\ n\ =\ 1 x2 % n = 1
( x 2 − 1 ) % n = 0 (x^2\ -\ 1)\ \%\ n\ =\ 0 (x2 − 1) % n = 0
x 2 − 1 = k n x^2\ -\ 1 = kn x2 − 1=kn
( x − 1 ) ( x + 1 ) = k n (x\ -\ 1)(x\ +\ 1)\ =\ kn (x − 1)(x + 1) = kn
然后设
( x + 1 ) = k 1 ∗ n 1 (x\ +\ 1)\ =\ k_1 * n_1 (x + 1) = k1∗n1
( x − 1 ) = k 2 ∗ n 2 (x\ -\ 1)\ =\ k_2 * n_2 (x − 1) = k2∗n2
k 1 ∗ k 2 = k k_1 * k_2 = k k1∗k2=k
n 1 ∗ n 2 = n n_1 * n_2 = n n1∗n2=n
我们枚举 n 1 n_1 n1并记为 a a a
那么
n 2 = n / a n_2\ =\ n\ /\ a n2 = n / a
( x + 1 ) = k 1 ∗ a (x\ +\ 1)\ =\ k_1\ *\ a (x + 1) = k1 ∗ a
我们再枚举 k 1 k_1 k1，记作 b b b
则 ( x + 1 ) = a ∗ b (x\ +\ 1)\ =\ a\ *\ b (x + 1) = a ∗ b
即 x = a ∗ b − 1 x\ =\ a\ *\ b\ -\ 1 x = a ∗ b − 1
将此式代入 ( x − 1 ) = k 2 ∗ n 2 (x\ -\ 1)\ =\ k_2 * n_2 (x − 1) = k2∗n2
得 ( a ∗ b − 1 ) = k 2 ∗ ( n / a ) (a\ *\ b\ -\ 1)\ =\ k_2\ *\ (n\ /\ a) (a ∗ b − 1) = k2 ∗ (n / a)
若 ( a ∗ b − 2 ) (a\ *\ b\ -\ 2) (a ∗ b − 2)为 ( n / a ) (n\ /\ a) (n / a)的倍数
则 x = a ∗ b − 1 x\ =\ a\ *\ b\ -\ 1 x = a ∗ b − 1为一组解
其余参考大爷博客
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;ll Ans[5000250];
ll n, m, t;void init(ll n1)
{for(ll k1 = 0; k1 <= n / n1; ++k1){m = n1 * k1 - 2;//处理(x-1)和(x+1)if(m % (n / n1) == 0)Ans[++t] = n1 * k1 - 1;m = n1 * k1 + 2;if(m % (n / n1) == 0)Ans[++t] = n1 * k1 + 1;}
}int main()
{scanf("%lld", &n);if(n == 1){printf("None\n"); return 0;}for(int i = 1; i <= (ll)sqrt(n); ++i)if(!(n % i))init(n / i);sort(Ans + 1, Ans + t + 1);t = 0;while(Ans[++t] <= 0);t--;while(Ans[++t] && Ans[t] <= n)if(Ans[t] != Ans[t - 1])printf("%lld\n", Ans[t]);return 0;}
这篇关于【模拟赛】【数论】2021.8.12.D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
