ADAGAME4 Spoj 错误答案

Question

Below is a Archive PROBLEM from SPOJ. Sample testCase is passing, but I am getting W/A on submission. I am missing some testCase(testCases). Need help to figure out what case I am missing and/or what I am doing wrong here.

Ada the Ladybug is playing Game of Divisors against her friend Velvet Mite Vinit. The game has following rules. There is a pile of N stones between them. The player who's on move can pick at least 1 an at most σ(N) stones (where σ(N) stands for number of divisors of N). Obviously, N changes after each move. The one who won't get any stones (N == 0) loses.

因为瓢虫艾达是位女士，所以她先行动。你能决定谁将成为赢家吗？假设两个玩家都发挥最佳。

输入

The first line of input will contain 1 ≤ T ≤ 10^5, the number of test-cases. The next T lines will contain 1 ≤ N ≤ 2*10^7, the number of stones which are initially in pile.

输出

Output the name of winner, so either "Ada" or "Vinit".

示例输入：
8
1
3
5
6
11
1000001
1000000
29

示例输出：
阿达
初始化
阿达
阿达
初始化
初始化
阿达
阿达

代码

import java.io.*;

public class Main
{
    public static int max_size = 2 * (int)Math.pow(10,7) + 1;
    //public static int max_size = 25;
    //public static int max_size = 2 * (int)Math.pow(10,6) + 1;
    public static boolean[] dp = new boolean[max_size];
    public static int[] lastPrimeDivisor = new int[max_size];
    public static int[] numOfDivisors = new int[max_size];
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        preprocess();
        
        int t = Integer.parseInt(br.readLine());
        while(t > 0)
        {
            int n = Integer.parseInt(br.readLine());
            if(dp[n] == true)
                System.out.println("Ada");
            else
                System.out.println("Vinit");
            t--;
        }
    }
    public static void markLastPrimeDivisor()
    {
        for(int i = 0 ; i < max_size ; i++)
        {
            lastPrimeDivisor[i] = 1;
        }
        for(int i = 2 ; i < max_size ; i += 2)
        {
            lastPrimeDivisor[i] = 2;
        }
        int o = (int)Math.sqrt(max_size);
        for(int i = 3 ; i < max_size; i++)
        {
            if(lastPrimeDivisor[i] != 1)
            {
                continue;
            }
            lastPrimeDivisor[i] = i;
            if(i <= o)
            {
                for(int j = i * i ; j < max_size ; j += 2 * i)
                {
                    lastPrimeDivisor[j] = i;
                }
            }
        }
        /*for(int i = 1 ; i < max_size ; i++)
            System.out.println("last prime of " + i + " is " + lastPrimeDivisor[i]);*/
    }
    
    public static void countDivisors(int num)
    {
        int original = num;
        int result = 1;
        int currDivisorCount = 1;
        int currDivisor = lastPrimeDivisor[num];
        int nextDivisor;
        while(currDivisor != 1)
        {
            num = num / currDivisor;
            nextDivisor = lastPrimeDivisor[num];
            if(nextDivisor == currDivisor)
            {
                currDivisorCount++;
            }
            else
            {
                result = result * (currDivisorCount + 1);
                currDivisorCount = 1;
                currDivisor = nextDivisor;
            }
        }
        if(num != 1)
        {
            result = result * (currDivisorCount + 1);
        }
        //System.out.println("result for num : " + original + ", " + result);
        numOfDivisors[original] = result;
    }

    public static void countAllDivisors()
    {
        markLastPrimeDivisor();
        for(int i = 2 ; i < max_size ; i++)
        {
            countDivisors(i);
            //System.out.println("num of divisors of " + i + " = " + numOfDivisors[i]);
        }
    }


    public static void preprocess()
    {
        countAllDivisors();
        dp[0] = dp[1] = dp[2] = true;
        for(int i = 3 ; i < max_size ; i++)
        {
            int flag = 0;
            int limit = numOfDivisors[i];
             //If for any i - j, we get false,for playing optimally
            //the current opponent will choose to take j stones out of the
            //pile as for i - j stones, the other player is not winning.
            for(int j = 1 ; j <= limit; j++)
            {
                if(dp[i - j] == false)
                {
                    dp[i] = true;
                    flag  = 1;
                    break;
                }
            }
            if(flag == 0)
                dp[i] = false;
        }
        
    }

}

Answer 1

您的 countDivisors() 函数中有一个细微的错误。它假设那 lastPrimeDivisor[num] – 顾名思义 – returns 给定参数的最大 个质因数。

然而，事实并非如此。例如，lastPrimeDivisor[num] = 2 对于所有偶数，或 lastPrimeDivisor[7 * 89] = 7。原因是在

public static void markLastPrimeDivisor()
{
    // ...
    for(int i = 3 ; i < max_size; i++)
    {
        // ...
        if(i <= o)
        {
            for(int j = i * i ; j < max_size ; j += 2 * i)
            {
                lastPrimeDivisor[j] = i;
            }
        }
    }
}

仅更新从 i * i 开始的数组元素。

所以 lastPrimeDivisor[num] 实际上是 num 的质因数，但不是一定是最大的。因此，计算 numOfDivisors[55447] 作为 8 而不是正确的值 6.

因此在countDivisors()中，num中的质因数的指数必须通过重复除法明确确定。

然后你可以使用除数函数乘法。这导致以下实施：

public static void countAllDivisors() {

    // Fill the `somePrimeDivisor` array:
    computePrimeDivisors();

    numOfDivisors[1] = 1;
    for (int num = 2 ; num < max_size ; num++) {
        int divisor = somePrimeDivisor[num];
        if (divisor == num) {
            // `num` is a prime
            numOfDivisors[num] = 2;
        } else {
            int n = num / divisor;
            int count = 1;
            while (n % divisor == 0) {
                count++;
                n /= divisor;
            }
            // `divisor^count` contributes to `count + 1` in the number of divisors,
            // now use multiplicative property:
            numOfDivisors[num] = (count + 1) * numOfDivisors[n];
        }
    }
}

ADAGAME4 Spoj 错误答案

ADAGAME4 Spoj Wrong Answer

java

algorithm

memoization

dynamic-programming