ChuVanKhanh's blog

How many solutions does the following equation have for given a b: 1/x+1/y=1/(a*b).
By ChuVanKhanh, history, 2 years ago, In English

My solution is to count the divisors of (a*b)^2 but a, b <= 1e6. In addition the problem has testcase <= 1e6. Can you help me?

  • Vote: I like it
  • +20
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
2 years ago, # |
← Rev. 12   Vote: I like it +19 Vote: I do not like it

since a and b are both less than 1e6, so I guess you can use sieve.

edit:
precomputation is around O(N) with a tiny constant factor (with euler sieve), as mentioned by ling_luo.
Each query is thus O(log(N)) since we need to iterate through all of the prime factors of the number. Total time complexity then would be O(N+Q*log(N)), which I guess should be well within TL. :D
sorry for my horrible grammar and really, way too many revisions.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    i tried using it but it time!

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Well the algorithm should get accepted because the time complexity is O(Q log N), maybe your implementation has some problems that made it TLE

      → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Obviously a number less than $$$10^6$$$ has at most $$$7$$$ distinct prime divisors. Let's denote $$$d=7$$$.

We can precompute the prime factorizations of numbers ranging from $$$1$$$ to $$$v=10^6$$$ in $$$O(vd)$$$ by Euler sieve.

We can know the factorization of $$$(ab)^2$$$ easily by the factorizations of $$$a$$$ and $$$b$$$.

Then we can know the number of divisors easily, which is sufficent enough to process $$$t=10^6$$$ queries.

Time Complexity: $$$O(vd+td)$$$.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Rwxy's solution is slightly different: he precomputes the smallest divisor instead of the whole factorization, and recompute the factorization for every query. The complexity, as mentioned by him, is $$$O(v+t\log v)$$$.

    We can optimize it to $$$O(v+td)$$$ by precomputing the smallest divisor $$$p$$$, the power of that $$$k$$$, and the next number(that is the number divided by $$$p^k$$$), that makes it faster.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 3   Vote: I like it +28 Vote: I do not like it

      thanks for telling me about the optimization!

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        You're welcome. That also optimizes my solution because $$$v$$$ (your $$$N$$$) can be set up to $$$5\times10^7$$$ and $$$t$$$ (your $$$Q$$$) can be set up to $$$5\times10^6$$$. (assuming around $$$10^8$$$ calculations per second)

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          How to sieve with the complexity is O(log n)

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            What do you mean by sieve? If you mean "recompute the factorization", we repeat dividing the number with the smallest prime divisor until it becomes $$$1$$$.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it 
              #include<bits/stdc++.h>
using namespace std;
const int N = 1e6+6;
int prime[N];
void sieve(){
    for(int i=1;i<=N;i++)
    {
        prime[i]=i;
    }
    for(int i=2;i<=sqrt(N);i++)
    {
        if(prime[i])
        {
            for(int j=i*i;j<=N;j+=i)
            {
                if(prime[j]==j) prime[j]=i;
            }
        }
    }
}
int main()
{
   sieve();
   short pow[N];
   int t;
   cin >> t;
   while(t--)
   {
        vector<int> need;
        int a, b;
        long long ans=1;
        cin >> a >> b;
        while(a!=1)
        {
            int count=0;
            int flags=prime[a];
            while(a%flags==0)
            {
                count++;
                a/=flags;
            }
            pow[flags] += count;
            need.push_back(flags);
        }
         while(b!=1)
        {
            int count=0;
            int flags=prime[b];
            while(b%flags==0)
            {
                count++;
                b/=flags;
            }
            pow[flags] += count;
            need.push_back(flags);
        }
        for(int i=0;i<need.size();i++)
        {
            ans*=(pow[need[i]]*2+1);
            pow[need[i]]=0;
        }
        cout << ans << endl;
   }
}

              Is my solution to this problem need to be optimized anymore? I think my method is so optimal

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                It is able to pass the problem, but not optimized. Your solution is $$$O(v\log v+q\log v)$$$, and can be optimized to $$$O(v\log \log v+q\log v)$$$ by replacing if(prime[i]) to if(prime[i]==i).

                If there's something wrong, remind me.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  whether the sieve of Eratosthenes or euler better ? should I replace my sieve with euler for better optimization. Can you show me how to optimize even more! If(a, b <=1e9) what should i do?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Euler sieve is $$$O(v)$$$, while Eratosthenes sieve is $$$O(v\log \log v)$$$. About the best solution I can come up with, I mentioned it above. I cannot solve the case where $$$a,b\le 10^9$$$.

                  → Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Why is "The number of solutions for the equation" equal to "Number of divisors of (a*b)^2 " ?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Rewriting the equation, we get $$$(x - ab)(y - ab) = a^2b^2$$$, and clearly, $$$x$$$ and $$$y$$$ must be positive, so the number of solution is simply $$$d(a^2b^2)$$$. AMC level algebraic manipulation I would say

    → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

If we have the prime factorization of $$$N$$$, then we can easily calculate the number of factors $$$N^2$$$ as power of each prime will be doubled. So, now the question is to get the prime factorization of $$$a*b$$$. For this we can separately factorize both $$$a$$$ and $$$b$$$ and keep the count of their primes in one $$$map$$$ using sieve.

My implementation using sieve is here .

A similar question can be found here .

→ Reply