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

abc-hits 题号:127 难度: 50 中英对照

The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 23 × 32 × 7, so rad(504) = 2 × 3 × 7 = 42.

We shall define the triplet of positive integers (a, b, c) to be an abc-hit if:

  1. GCD(a, b) = GCD(a, c) = GCD(b, c) = 1
  2. a < b
  3. a + b = c
  4. rad(abc) < c

For example, (5, 27, 32) is an abc-hit, because:

  1. GCD(5, 27) = GCD(5, 32) = GCD(27, 32) = 1
  2. 5 < 27
  3. 5 + 27 = 32
  4. rad(4320) = 30 < 32

It turns out that abc-hits are quite rare and there are only thirty-one abc-hits for c < 1000, with ∑c = 12523.

Find ∑c for c < 120000.

Solution

考虑利用暴力枚举的方法求解: 对于所有范围内(小于$120000$)的数,先计算出它的$rad$值,然后枚举所有可能的$a$和$b$($a< b$)的值,令$c=a+b$,依次判断条件: 1. $a$和$b$互质(这一点可以直接推出$a$和$a+b$互质、$b$和$a+b$互质) 2. $rad(a)rad(b)rad(a+b) < a+b$ 更进一步,若我们反过来枚举$c$值,由$a< b$知道$b>1$ 则$rad(b) \ge 2$,于是 $$ 2rad(a)rad(c) \le rad(a)rad(b)rad(c)< c $$ 可得 $$ rad(a) \le \frac{c}{2rad(c)} $$ 于是再按$rad(a)$从小到大的顺序枚举$a$值,此时枚举的上限为$rad(a) \le \frac{c}{2rad(c)}$ ,可以极大的降低算法所需时间。

Code

import java.util.Arrays;

public final class p127 {
    
    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" );
    }	
    
    private static final int LIMIT = 120000;
    
    static class Radical implements Comparable<Radical> {
        public int number, rad;
        public Radical(int rad, int number) {
            this.number = number;
            this.rad = rad;
        }
        public int compareTo(Radical other) {
            if (this.rad > other.rad) return 1;
            if (this.rad < other.rad) return -1;
            return Integer.compare(this.number,other.number);
        }
    }
    public static String run() {
    	Radical[] radicals = new Radical[LIMIT];
    	for (int i = 0; i < LIMIT; i++)
    	    radicals[i] = new Radical(1, i);
    	for (int i = 2; i < LIMIT; i++) {
    	    if (radicals[i].rad == 1) {
    	        radicals[i].rad = i;
    	        for (int j = i + i; j < LIMIT; j += i) {
    	            radicals[j].rad *= i;
    	        }
    	    }
    	}
        long sum = 0;
    	Radical[] sortedRadicals = new Radical[LIMIT];
    	for(int i=0;i<LIMIT;i++)
    		sortedRadicals[i]=new Radical(radicals[i].rad,radicals[i].number);
        Arrays.sort(sortedRadicals);
        for (int c = 3; c < LIMIT; c++) {
            long radc = radicals[c].rad;
            for(int i=1;i<LIMIT;i++){
            	Radical a=sortedRadicals[i];
                if ((long)a.rad*radc*2 > (long)c) break;
                int b = c-a.number;
                if(a.number>=b) continue;
                if ((long)a.rad * radicals[b].rad * radc < (long)c && gcd(a.rad, radicals[b].rad) == 1L){
                    sum += c;
                }
            }
        }
        return Long.toString(sum);
    }
    
    public static long gcd(long i, long j) {  
    	long k;   
        while ((k=i%j) != 0) {            
            i = j;  
            j = k;  
        }  
        return j;  
    }  
}
18407904
240ms