[BZOJ] 1406: [AHOI 2007] 비밀번호 박스
1249 단어 2007
제목: 구 $0 < = x < n, 1 < = n < = n < = 2, 000, 000, 000, 000, 그리고 x ^ 2 \ equiv 1 \ \ pmod {n} $의 모든 $x $
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<ll> s;
int main() {
ll n; scanf("%lld", &n);
for(int i=1; i*i<=n; ++i) if(n%i==0) {
ll a=i, b=n/i, x;
for(int k=0; b*k+1<n ; ++k) {
x=b*k+1; if((x+1)%a==0) s.insert(x);
}
for(int k=1; b*k-1<n; ++k) {
x=b*k-1; if((x-1)%a==0) s.insert(x);
}
}
for(set<ll>::iterator it=s.begin(); it!=s.end(); ++it)
printf("%lld
", *it);
return 0;
}
좋 은 신의 문제
먼저 간단 하면 $(x + 1) (x - 1) = kn $를 쉽게 얻 을 수 있 습 니 다. 그래서 문 제 를 풀 었 습 니 다 = =, 신 제 는 설명 하지 않 습 니 다 = = =
그래서 $n | (x + 1) (x - 1) $를 얻 었 습 니 다.
$n = ab $를 설정 하면 $ab | (x + 1) (x - 1) \ Rightarrow \ left (a | (x + 1) \ land b | (x - 1) \ \ right) \ lor \ left (a | (x - 1) \ land b | (x + 1) \ right) $
나 는 내 가 그 충분 성 을 증명 할 수 없다 는 것 을 알 았 다. 어떻게 해, QAQ.
그래서 $O (\ sqrt {n} ln \ sqrt {n}) $면 됩 니 다 = =
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BZOJ] 1052: [HAOI 2007] 덮어 쓰기 문제 (욕심)욕심 은 모든 점 을 포위 할 수 있 는 가장 작은 행렬 을 찾 아 네 개의 뿔 을 정사각형 으로 늘 어 놓 는 것 이다. 가장 좋 은 정사각형 의 정점 은 모든 점 을 둘 러 싼 사각형 의 한 각 (그렇지 않 으 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.