2

目前，对于hackerearth.com上提供的一些测试用例，以下问题需要3.008**秒才能执行，其中允许的时间是3.0秒，所以我得到时间限制错误。请帮助减少执行时间。

问题：Alice 刚刚学会了将两个整数相乘。他想将两个整数 X 和 Y 相乘以形成一个数 Z。为了使问题变得有趣，他将选择 [1,M] 范围内的 X 和 [1,N] 范围内的 Y。帮助他找到他可以做到这一点的方式。

输入

输入的第一行是测试用例的数量 T。接下来是 T 行。每行有三个空格分隔的整数，数字 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

8

这里性能的主要问题是您的内部循环对10^12迭代进行了处理。您可以将其减少一百万次sqrt(z) <= 10^6。

这里的诀窍是要注意 Alice 可以写z = x * y当且仅当他可以写z = y * x。此外，要么x <= sqrt(z)要么y <= sqrt(z)。使用这些事实，您最多只能迭代平方根z来计算所有案例。

于 2013-10-01T16:35:14.563 回答
5

我相信这应该可以完成工作（来自@zch's answer的想法）：

#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) 返回 1; 将始终返回 1。为什么要将 A 与 B (a/b) 相除，然后将结果乘以 B。这是模棱两可的，因为当您说 (a/b) * (b) 时，您的答案将是 A。B`s 会互相抵消，你只剩下 A 作为你的答案。所以基本上你是在比较 A == A，这是真的。
于 2013-10-01T16:55:21.023 回答