-1

问题如下：

There is one friendly number and N unfriendly numbers. We want to find how many numbers are there which exactly divide the friendly number, but does not divide any of the unfriendly numbers.

Input Format:
The first line of input contains two numbers N and K seperated by spaces. N is the number of unfriendly numbers, K is the friendly number.
The second line of input contains N space separated unfriendly numbers.

Output Format:
Output the answer in a single line.

Constraints:
1 <= N <= 10^6
1 <= K <= 10^13
1 <= unfriendly numbers <= 10^18

Sample Input:
8 16
2 5 7 4 3 8 3 18

Sample Output:
1

Explanation :
Divisors of the given friendly number 16, are { 1, 2, 4, 8, 16 } and the unfriendly numbers are {2, 5, 7, 4, 3, 8, 3, 18}. Now 1 divides all unfriendly numbers, 2 divide 2, 4 divide 4, 8 divide 8 but 16 divides none of them. So only one number exists which divide the friendly number but does not divide any of the unfriendly numbers. So the answer is 1.

以下是我的 C# 解决方案：

class Solution
{
    static void Main(string[] args)
    {
        string firstLine = Console.ReadLine();
        string[] firstLineItems = firstLine.Split(' ');

        ulong friendlyNum = Convert.ToUInt64(firstLineItems[1]);
        int noOfunf = Convert.ToInt32(firstLineItems[0]);

        string secondLine = Console.ReadLine();
        string[] secondLineItems = secondLine.Split(' ');

        List<ulong> unfriendlyNumbersArray = new List<ulong>(noOfunf);

        foreach (string str in secondLineItems)
        {
            unfriendlyNumbersArray.Add(Convert.ToUInt64(str));
        }

        List<ulong> divisors = CalculateDivisors(friendlyNum);

        Console.WriteLine(finalCall(divisors, unfriendlyNumbersArray));
    }

    private static List<ulong> CalculateDivisors(ulong number)
    {
        List<ulong> factors = new List<ulong>();

        for (ulong factor = 1; factor * factor <= number; ++factor)
        {
            if (number % factor == 0)
            {
                factors.Add(factor);
                if (factor * factor != number)
                {
                    factors.Add(number / factor);
                }
            }
        }
        return factors;
    }

    private static long finalCall(List<ulong> divisors, List<ulong> unfriendlyNumbersArray)
    {
        long output = 0;
        var unfriendlyNumbers = (from i in unfriendlyNumbersArray select i).Distinct();

        foreach (ulong divisor in divisors)
        {
            var test = unfriendlyNumbers.Where(number => number % divisor == 0).ToList();
            output += (test.Count == 0) ? 1 : 0;
        }
        return output;
    }
}

只有前 3 个测试用例通过。第 4 个被杀，第 5 个和第 6 个给我解析字符串的异常。

第 5 次和第 6 次除外：

Unhandled Exception: System.FormatException: Input string was not in the correct format
    at System.UInt64.Parse (System.String s) [0x00000] in :0 
    at System.Convert.ToUInt64 (System.String value) [0x00000] in :0 
    at Solution.Main (System.String[] args) [0x00000] in :0 
    [ERROR] FATAL UNHANDLED EXCEPTION: System.FormatException: Input string was not in the     correct format
    at System.UInt64.Parse (System.String s) [0x00000] in :0 
    at System.Convert.ToUInt64 (System.String value) [0x00000] in :0 
    at Solution.Main (System.String[] args) [0x00000] in :0
4

2 回答 2

1

您应该使用Split带StringSplitOptions参数并通过的重载RemoveEmptyEntries。否则，如果输入被多个空格分隔，则数组包含空字符串，无法解析。

于 2012-05-11T09:28:47.187 回答
0

我能够根据以下链接解决此问题。上面链接的作者对数论的深入理解让我感到非常惊讶。上面的算法没有错。只是它不会在 5 秒内解决问题，这是我们遵守的约束。

于 2012-08-24T06:50:02.443 回答