ADAGAME4 Spoj错误答案

Question

下面是SPOJ的一个归档问题。示例测试用例通过了，但我在提交时得到了W/A。我缺少一些测试用例（testCase）。需要帮助来找出我错过了什么案例和/或我做错了什么。

瓢虫艾达正在和她的朋友维尼特玩除数游戏。这个游戏有以下规则。他们之间有一堆石头。移动中的玩家可以选择至少1块，最多σ（N）块石头（其中σ（N）代表N的除数）。显然，N在每次移动后都会发生变化。得不到任何石头（N==0）的人输了。

因为瓢虫艾达是个淑女，所以她先动。你能决定谁获胜吗？假设两个玩家都玩得很好。

输入

输入的第一行将包含1≤ T≤ 10^5，测试用例的数量。接下来的T行将包含1≤ N≤ 2*10^7，最初堆放的石块数量。

输出

输出获胜者的名字，所以可以是“Ada”或“Vinit”。

样本输入：
8
1
3
5
6
11
1000001
1000000
29

示例输出：
Ada
Vinit
Ada
Ada
Vinit
Vinit
Ada
Ada

密码

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]-如名称所示-

然而，事实并非如此。例如，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的一些素因子，但不一定是最大的。因此，numof除数[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];
        }
    }
}