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

Investigating Gaussian Integers 题号:153 难度: 65 中英对照

As we all know the equation x2=-1 has no solutions for real x.
If we however introduce the imaginary number i this equation has two solutions: x=i and x=-i.
If we go a step further the equation (x-3)2=-4 has two complex solutions: x=3+2i and x=3-2i.
x=3+2i and x=3-2i are called each others' complex conjugate.
Numbers of the form a+bi are called complex numbers.
In general a+bi and abi are each other's complex conjugate.

A Gaussian Integer is a complex number a+bi such that both a and b are integers.
The regular integers are also Gaussian integers (with b=0).
To distinguish them from Gaussian integers with b ≠ 0 we call such integers "rational integers."
A Gaussian integer is called a divisor of a rational integer n if the result is also a Gaussian integer.
If for example we divide 5 by 1+2i we can simplify in the following manner:
Multiply numerator and denominator by the complex conjugate of 1+2i: 1−2i.
The result is .
So 1+2i is a divisor of 5.
Note that 1+i is not a divisor of 5 because .
Note also that if the Gaussian Integer (a+bi) is a divisor of a rational integer n, then its complex conjugate (abi) is also a divisor of n.

In fact, 5 has six divisors such that the real part is positive: {1, 1 + 2i, 1 − 2i, 2 + i, 2 − i, 5}.
The following is a table of all of the divisors for the first five positive rational integers:

n Gaussian integer divisors
with positive real part
Sum s(n) of
these divisors
111
21, 1+i, 1-i, 25
31, 34
41, 1+i, 1-i, 2, 2+2i, 2-2i,413
51, 1+2i, 1-2i, 2+i, 2-i, 512

For divisors with positive real parts, then, we have: .

For 1 ≤ n ≤ 105, ∑ s(n)=17924657155.

What is ∑ s(n) for 1 ≤ n ≤ 108?


Solution

首先考虑有理整数,注意到下表: n 是有理整数的约数 1 1 2 1 2 3 1 3 4 1 2 4 5 1 5 …… 注意到对于$n=5$的情况,包含5个1、2个2、1个3、1个4、1个5。 实际上对于$n$,所有$\leq n$的数的约数包含有理整数$i$的数量为$\left[ \frac{n}{i}\right]$,方括号为高斯函数,表示向下取整。 设这个数量为$f(n)$,则$f(n)=\sum_{i=1}^n \left[ \frac{n}{i}\right]$。 再考虑约数是形如$a\times (1+i)$的数量: $$\frac{n}{a\times(1+i)}=\frac{n}{2a}\times (1-i)$$ 所以所有$\leq n$的数的约数形如$a\times (1+i)$的数量恰好等于$f\left( \frac{n}{2}\right)$。 另外,所有$\leq n$的数的约数形如$a\times (1-i)$的数量和上式相等。 最后考虑约数是形如$a+bi$的数量,这里$gcd(a,b)=1$。 直接枚举这一部分即可。

Code

public final class p153 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }

    static public String run() {
		int L = 100000000;
		long sum = f(L) + 2 * f(L / 2);
		for (int a = 1; a * a <= L; ++a)
			for (int b = a + 1; b * b <= L - a * a; ++b)
				if (gcd(a, b) == 1)
					sum += 2 * (a + b) * f(L / (a * a + b * b));
		return ""+sum;
    }

	static int gcd(int a, int b) {
		while (a != 0) {
			b %= a;
			int t = a;
			a = b;
			b = t;
		}
		return b;
	}

	static long f(int M) {
		long f = 0;
		for (int i = 1; i <= M; ++i)
			f += (M / i) * i; // yes!
		return f;
	}
	
}
17971254122360635
5811ms