문제는 숫자의 제수를 찾는 것입니다.
전의-
for 10
년 = 4
1,2,5,10은 제수이기 때문에
즉 그들은 요인입니다
제약은 num <= 10 ^ 6입니다.
나는 같은 코드를 구현했지만 TLE를 얻었다!
여기 내 코드입니다
int isprime[MAX];
void seive()
{
int i,
j;
isprime[0] = isprime[1] = 1;
for (i = 4; i < MAX; i += 2)
isprime[i] = 1;
for (i = 3; i * i < MAX; i += 2) {
if (!isprime[i]) {
for (j = i * i; j < MAX; j += 2 * i)
isprime[j] = 1;
}
}
}
int main()
{
seive();
int t;
long long num;
scanf("%d", & t);
while (t--) {
scanf("%lld", & num);
cnt = 0;
for (j = 1; j * j <= num; j++) {
if (num % j == 0) {
cnt++;
if (num / j != j)
cnt++;
}
printf("%lld\n", cnt);
}
return 0;
}
누군가 내가 그것을 최적화하도록 도울 수 있습니까?
나는 또한 그것에 대해 검색했지만 성공하지 못했습니다.
그러니 제발 도와주세요.
당신은 이것을 수학적으로 계산해 볼 수 있습니다 (나는 이것이 더 빠르거나 쉬울 것이라고 확신하지 않습니다). 기본적으로 숫자의 소인수 분해가 주어지면 너무 많은 문제없이 제수를 계산할 수 있어야합니다.
입력이 있으면 x다음과 같이 분해됩니다.
x = p1^a1 * p2^a2 * ... pn^an
그런 다음 제수는
prod(ai + 1) for i in 1 to n
그런 다음 가장 작은 소수 <sqrt (x)를 찾아서 소수만 남을 때까지 나누었습니다. 체가 여전히 유용 할 수 있으며 어떤 종류의 입력을 받게 될지 모르겠습니다.
이제 위의 진술이 말하는 것을 고려하십시오 : 소인수 분해의 거듭 제곱 (+1)의 곱에서 제수 수. 따라서 결과가 소수인지에만 신경을 쓴다면 소수 또는 소수의 거듭 제곱 인 숫자 만 고려해야합니다. 그리고 그 안에서 a1 + 1이 소수가되는 거듭 제곱 만 고려하면됩니다.
그러면 검색 공간이 크게 줄어들 것입니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다