SPOJ DIVSUM2 PollardRho 康某

大意：给出一个数，求他的所有因子的和（不包括自己）

首先，先算上他自己，问题转化为求所有因子的和

根据唯一分解定理，设数为N，则质因子为P1P2...PK，指数设为A1A2...AK

则所有因子，则是P1位指数取【0，A1】，P2位取【0，A2】…………

譬如20 = 2 ^2 * 5，则因子为 1（2^0 * 5^0），2（2^1 * 5 * 0），4（2 ^ 2 * 5 ^ 0），5（2^0 * 5 ^ 1），10（2^1 * 5 ^ 1），20（2^2* 5 ^ 1）

提取一下 = 2^0 *(5 ^ 0 + 5 ^ 1) + 2^1 *(5 ^ 0 + 5 ^ 1) + 2^2 *(5 ^ 0 + 5 ^ 1)

= (2 ^ 0 + 2 ^ 1 + 2 ^ 2) * (5 ^ 0 + 5 ^ 1) = 42

挺对……于是公式可以得出……就是每个因子等比序列求和一下，然后求乘积得到所有因子相加的和，最后减去N自己即可……

问题在于怎么质因子分解……这个数很大，很难做……于是，我们要使用 PollardRho 算法……

另外有一点要注意……Java不是没有函数传地址……Java相当于传的是个Vector* ret，如果你想修改他，ret = XXX 是没戏的…… 而ret.set(XXX)是正解……

见第33行……

分解之后，排序，统计即可

import java.math.BigInteger;
import java.security.SecureRandom;
import java.io.*;
import java.util.*;



class PollardRho {
    private final static BigInteger ZERO = new BigInteger("0");
    private final static BigInteger ONE  = new BigInteger("1");
    private final static BigInteger TWO  = new BigInteger("2");
    private final static SecureRandom random = new SecureRandom();

    public static BigInteger rho(BigInteger N) {
        BigInteger divisor;
        BigInteger c  = new BigInteger(N.bitLength(), random);
        BigInteger x  = new BigInteger(N.bitLength(), random);
        BigInteger xx = x;

        // check divisibility by 2
        if (N.mod(TWO).compareTo(ZERO) == 0) return TWO;

        do {
            x  =  x.multiply(x).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            divisor = x.subtract(xx).gcd(N);
        } while((divisor.compareTo(ONE)) == 0);

        return divisor;
    }

    public static void factor(BigInteger N, Vector<Long> ret) {
        if (N.compareTo(ONE) == 0) return;
        if (N.isProbablePrime(20)) { ret.add(N.longValue()); return; }
        BigInteger divisor = rho(N);
        factor(divisor,ret);
        factor(N.divide(divisor),ret);
    }
}

class Main {
    public static void main(String args[]) {
        new Main().work();
    }

    void factor(int n, Vector<Long> ret) {
    }

    void work() {
        try {
            BufferedReader in = new BufferedReader(
                    new InputStreamReader(System.in));
            int nn = Integer.parseInt(in.readLine());
            while (nn-- > 0) {
                long n = Long.parseLong(in.readLine());
                Vector<Long> ret = new Vector<Long>();
                PollardRho.factor(BigInteger.valueOf(n),ret);
                Collections.sort(ret);
                // System.err.println(ret);

                Long ans = 1L;
                for (int i = 0; i < ret.size(); i++) {
                    Long pow = 1L;
                    Long sum = 1L;
                    for (int j = i; j < ret.size() && ret.get(j).equals(ret.get(i));j++) {
                        pow *= ret.get(j);
                        sum += pow;
                        i = j;
                    }
                    // System.err.printf("%d %d\n",pow,sum);
                    ans *= sum;
                }
                System.out.println(ans - n);
            }
        } catch (Exception e) {}
    }
}