2

現在、次の問題は、hackerearth.com で提供されているテストケースの実行に 3.008** 秒かかっており、許可されている時間は 3.0 秒であるため、時間制限エラーが発生します。実行時間の短縮にご協力ください。

問題: アリスは 2 つの整数の乗算を学習したところです。彼は 2 つの整数 X と Y を掛け合わせて数 Z を形成したいと考えています。問題を面白くするために、範囲 [1,M] で X を選択し、範囲 [1,N] で Y を選択します。彼がこれを行うことができる方法。

入力

入力の最初の行は、テスト ケースの数 T です。その後に T 行が続きます。各行には、スペースで区切られた 3 つの整数、数値 Z、M、および N があります。

出力

テスト ケースごとに、方法の数である単一の整数を出力します。

制約 1 <= T <= 50 1 <= Z <= 10^12 1 <= M <= 10^12 1 <= N <= 10^12

コード：

#include <iostream>
using namespace std;


int chk_div(long long a,long long b)
{
if(((a/b) * (b) )==a)return 1;
return 0;
}

int main()
{
   int t;
   long  i,j,count;
   long  n,m,z;
   cin>>t;
   while(t--)
   {count=0;
    cin>>z>>m>>n;
    if(m>z)m=z;
    if(n>z)n=z;
    if (m>n)m=n;
    for(i=1;i<=m;i++)
    {
         if(chk_div(z,i))count++;       
     }

   cout<<count<<"\n";
   }
return 0;
}
4

4 に答える 4

5

これで仕事が完了するはずだと思います（@zchの回答からのアイデア）：

#include <iostream>
#include <cmath>

auto MAX = [] (int A, int B) -> bool { return A > B ? A : B; };
auto MIN = [] (int A, int B) -> bool { return A < B ? A : B; };

using std::cout;
using std::cin;

int main() {
    long long Z, M, N, T, low, high, temp, div;
    int ans;

    for (cin >> T; T--; ) {

        cin >> Z >> M >> N;
        temp = MIN(M, N);
        low = MIN(sqrt(Z), temp);
        high = MAX(M, N);

        for( ans = 0; low > 0 && (Z / low) <= high; --low ) {
            if ( Z % low == 0) {
                ++ans;
                div = Z / low;
                ans += (div != low && div <= temp);
            }
            //cout << temp << " * " << Z / temp << " = " << Z << "\n";
        }
        cout << ans << "\n";
    }

    return 0;
}

少しずつコメント追加予定

コメント付きのコード:

#include <iostream>
#include <cmath>

auto MAX = [] (int A, int B) -> bool { return A > B ? A : B; };
auto MIN = [] (int A, int B) -> bool { return A < B ? A : B; };

using std::cout;
using std::cin;

int main() {
    long long Z, M, N, T, low, high, temp, div;
    int ans;

    for (cin >> T; T--; ) {

        cin >> Z >> M >> N;
        temp = MIN(M, N);
        low = MIN(sqrt(Z), temp);//Lowest value <--We start iteration from this number
        high = MAX(M, N); //Maximum value

        for( ans = 0; low > 0 && (Z / low) <= high; --low ) {

            //Number of things going on in this for-loop
            //I will start by explaining the condition:
                //We want to keep iterating until either low is below 1
                // or when the expression (Z / low) > high.
                //Notice that as the value of low approaches 0,
                //the expression (Z / low) approaches inf
            if ( Z % low == 0) {

                //If this condition evaluates to true, we know 2 things:
                    /*Z is divisible by this value of low and 
                        low is in the range of MIN(M,N) <--true*/
                    /*Because of our condition, (Z / low) is
                        within the range of MAX(M, N) <--true*/
                ++ans;
                div = Z / low;

                //This second part checks if the opposite is true i.e.
                    /*the value of low is in the range of
                        MAX(M, N) <--true*/
                    /*the value (Z / low) is in the range of
                        MIN(M, N) <--true only in some cases*/
                ans += (div != low && div <= temp);

                //(div != low) is to avoid double counting
                /*An example of this is when Z, M, N have the values:
                    1000000, 1000000, 1000000
                    The value of low at the start is 1000 */
            }
        }
        cout << ans << "\n";
    }
    return 0;
}
于 2013-10-01T18:05:21.747 に答える
2

実際には、別の方法で問題を解決する必要があります。

プライム分解を見つけます。

だから素数Z = A^a * B^b * ... * P^pでA, B, .., P

したがって、 から可能性の数を計算するだけですa, b, ... p。

(したがって、結果は(1 + a) * (1 + b) * ... * (1 + p)M&N 制約に依存します)。

于 2013-10-01T17:20:48.080 に答える
-1
  • あなたの if(((a/b) * (b) ) == a) return 1; は常に 1 を返します。なぜ A を B で割って (a/b)、その結果を B で乗算するのですか。(a/b) * (b) と言うと答えが A になるため、これはあいまいです。B は互いに打ち消し合い、答えとして A が残ります。したがって、基本的には、A == A であるかどうかを比較しています。これは true です。
于 2013-10-01T16:55:21.023 に答える