PHP를 사용하여 가장 큰 홀수 약수의 합 찾기

이 글에서는 PHP를 사용하여 가장 큰 홀수 약수의 합을 구하는 방법을 소개합니다. 도움이 필요한 친구들이 모두 참고할 수 있기를 바랍니다.

Xiao Yi는 정수론을 좋아하며 숫자의 홀수 약수에 관심이 많습니다. 어느 날 Xiaoyi는 다음과 같은 문제에 직면했습니다. 함수 f(x)를 x의 가장 큰 홀수 약수로 정의하고 x는 양의 정수입니다. 예: f(44) = 11.

이제 N이 주어지면 f(1) + f(2) + f(3)…….f(N)

예: N = 7을 찾아야 합니다.

f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 1 + 1 + 3 + 1 + 5 + 3 + 7 = 21

Xiaoyi는 이 문제를 계산하는 데 어려움을 겪었으며 그를 도울 수 있는 알고리즘을 설계해야 합니다.

<?php
$num = trim(fgets(STDIN));

function jNum($num){
        $m = $num/2;
        $res = 1;
        if($num&0x1 == 1){//如果他本身就是个奇数，那么他的最大奇约数就是他本身
                $res = $num;
                goto HELL;
        }
        for($i = 1; $i<=$m; $i=$i+2){//如果不是，那么就从1开始一直往上除，每次+2（奇数）
                if($num%$i==0){
                        $res = $i;
                }
        }
        HELL:
        return $res;
}

function jNum2($num)
{
        $res = 0;

        for($i=1;$i<=$num;$i++){
                if(($i&0x1) == 1){//如果他本身就是个奇数，那么他的最大奇约数就是他本身
                        $res+=$i;
                }else{
                        $n = $i;
                        while(true){//优化，从最大的数开始往下除
                                $n = $n>>1;
                                if(($n&0x1) == 1){
                                        $res+=$n;
                                        break;
                                }
                        }
                }
        }

        HELL:
        return $res;
}

function jNum3($num){//公式法
        if($num == 1){
                return 1;
        }
        if(($num&0x1) == 0){
                return jNum3($num>>1)+$num*$num/4;
        }else{
                return jNum3($num-1)+$num;
        }

}
//$sum = 0;
//for($i = 1; $i<=$num; $i++){
//      $sum+=jNum($i);
//}
//echo $sum;

//echo jNum2($num);

echo jNum3($num);

기존의 생각으로 시작하세요. 방법 1은 디버깅을 하다가 항상 타임아웃이 발생하는데, 방법 2로 바꿔도 여전히 타임아웃이 발생합니다.

생각을 바꾸세요. .

sum(i)를 구하는 과정에서 i가 홀수이면 바로 찾을 수 있는데, 이는 i 자체, 즉 f(i) = i입니다.

문제는 모든 f(i)의 합을 구하는 것입니다. i는 짝수입니다.

가장 큰 홀수 약수이므로 f(2k) = f(k)이므로 f(2) + f(4) + … + f(2k) = f(1) + f(2) + … + f(k);

그래서 수학적 귀납법

을 통해 구할 수 있는 일반식을 생각하는 것은 쉽지 않습니다. . . 그런 BT 질문입니다. .

이 기사는 다음에서 복제되었습니다: https://blog.csdn.net/qq_28602957/article/details/77914402

권장 학습: PHP 비디오 튜토리얼

위 내용은 PHP를 사용하여 가장 큰 홀수 약수의 합 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!