[LuoguP1221] 최대 인수
[Luogu1221] 최대 인수(Link)
구간 [L, R] 에서 가장 많은 개수와 그것의 개수를 구하다.
이 문제는 언뜻 보기에는 어렵지 않은 문제였지만 조금만 생각해 보니 응, 바보 문제였어.이게 유일한 느낌이야, 왜냐고 묻지 마.
우선 함수\(F (X)\) 는\(X\) 의 개수를 나타냅니다.제목은\([L, R]\) 의\(F (X) max\) 와 이 수를 구해야 합니다.우선 각 개수\(Data[i]\)에는 다음과 같은 기본적인 특성이 있음을 알아야 합니다.
\(Data[i] = Prime 1^{M 1}\times Prime 2^{M 2}\times...\times Prime N^{M N}\), 언어는 임의의 i를 여러 질수의 몇몇 차방의 곱셈으로 분해할 수 있음을 나타낸다. 우리가 얻는 것\(F(X)=(M 1+1)\times(M 2+1)\times...\times (M_N + 1)\).
이로써 검색의 과정을 질인수 분해에서 질인수 상승으로 바꾸면 검색할 때 질인수만 검색하면 되고 질인수의 개수를 기록하면 된다.물론 단순히 이렇게 하면 (T\) 떨어질 수 있으니 다음에 가지치기를 세어 보세요.
#include
#include
#include
#include
#include
using namespace std ;
typedef long long LL ;
const int MAXN = 500010 ;
const int MAXM = 40000 ;
int L, R, Ans, Max, Prime[MAXN] ;
bool NotP[MAXN] ; int Tot ;
inline void Dfs(LL H, LL N, LL Now) {
if (H > Tot || N > R) return ;
int K = (int)(log(R / double(N)) / log(double(Prime[H]))) ;
if (Now * (1 << K) < Ans) return ;
if (N >= L && (Now > Ans || (Now == Ans && N < Max)))
Ans = Now, Max = N ;
LL X = 1 ;
for (int i = 1 ; i <= K ; i ++) X *= Prime[H] ;
for (int i = K + 1 ; i >= 1 ; i --) {
Dfs(H + 1, N * X, Now * i) ;
X /= Prime[H] ;
} return ;
}
int main() {
scanf("%d %d", & L, & R) ;
if (L == R && L == 1) {
printf("Between %d and %d, 1 has a maximum of 1 divisors.
", L, R);
return 0 ;
}
for (int i = 2 ; i <= MAXM ; i ++) {
if (! NotP[i]) {
Prime[++ Tot] = i ;
for (int j = i << 1 ; j <= MAXM ; j += i)
NotP[j] = true ;
}
}
if (R - L <= 10000) {
for (int i = L ; i <= R ; i ++) {
int T = 2 ;
for (int j = 2 ; j * j <= i ; j ++) {
if (j * j == i) T ++ ;
else if (i % j == 0) T += 2 ;
} if (T > Ans) Ans = T, Max = i ;
}
}
else Dfs(1, 1, 1) ;
printf("Between %d and %d, %d has a maximum of %d divisors.
", L, R, Max,Ans);
return 0 ;
}
전재 대상:https://www.cnblogs.com/Yeasio-Nein/p/P1221.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
