当前位置:首页 » Project Euler » 详细页

Square remainders 题号:120 难度: 25 中英对照

Let r be the remainder when (a−1)n + (a+1)n is divided by a2.

For example, if a = 7 and n = 3, then r = 42: 63 + 83 = 728 ≡ 42 mod 49. And as n varies, so too will r, but for a = 7 it turns out that rmax = 42.

For 3 ≤ a ≤ 1000, find rmax.

Solution

现在的问题是对于一个给定的$a$,求指定的n能使$~(a+1)^{n}+(a-1)^{n}~$除以$~a^{2}~$的余数最大。 对于任意的$~n \geq 3~$运用二项式定理 $$ (a+1)^{n}=1^{n}+C_n^1 a1^{n-1}+ C_n^{2}a^{2}1^{n-2}+\cdots $$ $$ (a-1)^{n}=(-1)^{n}+C_n^1 a(-1)^{n-1}+ C_n^{2}a^{2}(-1)^{n-2}+\cdots $$ 其中 $(a+1)^{n}$ 除以 $a^2$ 的余数是 $1+an$ ,因为$~a^{n} \equiv 0 ~mod ~a^2~,\forall n \geq 3~$. 同样可得$~(a-1)^{n}~$除以$~a^2~$的余数是$~(-1)^{n}+(-1)^{n-1}an~,$当$~n~$为偶数时,余数为$~1-an~$,当$~n~$为奇数时,余数为$~an-1.~$于是$~(a+1)^{n}+(a-1)^{n}~$除以$~a^2~$,当$~n~$为偶数时,余数为$~2~$,当$~n~$为奇数时,余数为$~2an.~$ 下面我们考虑当$~n~$为奇数时,余数最大为多少.由于$$\frac{2a*n}{a^2}=\frac{2n}{a}$$ 问题变成考虑$~2n~$除$~a~$的余数, 当$~a~$为偶数时,当$~n=a/2-1~$时,余数为$~a-2~,$ 当$~a~$为奇数时,当$~n=(a-1)/2~$时,余数为$~a-1~.$ 综上,当$~a~$为偶数时,余数为$~a(a-2)~,$ 当$~a~$为奇数时,余数为$~a(a-1)~.$

Code

using System;
namespace euler
{
    class Problem120
    {
        public static void Main(string[] args)
        {
            var start = DateTime.Now;
            var result = Run();
            var end = DateTime.Now;
            Console.WriteLine(result);
            Console.WriteLine("{0} ms", (end - start).TotalMilliseconds);
            Console.Read();
        }
        public static long Run()
        {
            int sum = 0;
            for (int a = 3; a <= 1000; a = a + 2)
                sum = sum + a * (a - 1);
            for (int a = 4; a <= 1000; a = a + 2)
                sum = sum + a * (a - 2);
            return sum;
        }
    }
}
333082500
1 ms
public class p100 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        long result = run();
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }
    public static long run() {
         int sum = 0;
         for (int a = 3; a <= 1000; a = a + 2)
             sum = sum + a * (a - 1);
         for (int a = 4; a <= 1000; a = a + 2)
             sum = sum + a * (a - 2);
         return sum;
    }
}
333082500
0ms