Ermitteln Sie mit PHP die Summe der größten ungeraden Teiler

In diesem Artikel erfahren Sie, wie Sie mit PHP die Summe der größten ungeraden Teiler ermitteln. Es hat einen gewissen Referenzwert. Freunde in Not können sich darauf beziehen. Ich hoffe, es wird für alle hilfreich sein.

Xiao Yi ist ein Enthusiast der Zahlentheorie und interessiert sich sehr für die ungeraden Teiler einer Zahl. Eines Tages stieß Xiaoyi auf ein solches Problem: Definieren Sie die Funktion f (x) als den größten ungeraden Teiler von x, und x ist eine positive ganze Zahl. Zum Beispiel: f(44) = 11.

Wenn wir nun ein N haben, müssen wir f(1) + f(2) + f(3) finden…….f(N)

Zum Beispiel: N = 7

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

Xiao Yi ist bei der Berechnung dieses Problems auf Schwierigkeiten gestoßen und möchte, dass Sie einen Algorithmus entwerfen, der ihm hilft.

<?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);

Beginnen Sie mit der konventionellen Denkweise, bei der es immer zu einer Zeitüberschreitung kommt. Wenn ich sie auf Methode 2 ändere, gibt es immer noch eine Zeitüberschreitung.

Ändern Sie Ihr Denken. .

Wenn i eine ungerade Zahl ist, können Sie bei der Ermittlung der Summe (i) diese direkt finden, nämlich i selbst, d. h. f(i) = i.

Das Problem besteht darin, die Summe aller f(i) zu finden, i ist eine gerade Zahl.

Weil es der größte ungerade Teiler ist, also f(2k) = f(k), also f(2) + f(4) + … + f(2k) = f(1) + f( 2 ) + … + f(k);

Daher ist es nicht einfach, sich die allgemeine Formel

mithilfe mathematischer Induktion auszudenken. . . So eine BT-Frage. .

Dieser Artikel ist reproduziert von: https://blog.csdn.net/qq_28602957/article/details/77914402

Empfohlenes Lernen: PHP-Video-Tutorial

Das obige ist der detaillierte Inhalt vonErmitteln Sie mit PHP die Summe der größten ungeraden Teiler. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!