-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を取り、を渡すオーバーロードを使用する必要があります。それ以外の場合、入力が複数のスペースで区切られている場合、配列には解析できない空の文字列が含まれます。StringSplitOptionsRemoveEmptyEntries

于 2012-05-11T09:28:47.187 に答える
0

私は次のリンクに基づいてこの問題を解決することができました。上記のリンクの著者の数論の深い理解に本当に驚いていました。上記のアルゴリズムに問題はありません。それが5秒以内に問題を解決しないというだけで、私たちが守っている制約です。

于 2012-08-24T06:50:02.443 に答える