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, 23 months 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?
»
23 months 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 MatrixGroup.
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
  • »
    »
    23 months ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    i tried using it but it time!

    → Reply
    • »
      »
      »
      23 months 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
»
23 months 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
  • »
    »
    23 months 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
    • »
      »
      »
      23 months ago, # ^ |
      ← Rev. 3   Vote: I like it +28 Vote: I do not like it

      thanks for telling me about the optimization!

      → Reply
      • »
        »
        »
        »
        23 months 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
        • »
          »
          »
          »
          »
          23 months ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            23 months 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
            • »
              »
              »
              »
              »
              »
              »
              23 months 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
              • »
                »
                »
                »
                »
                »
                »
                »
                23 months 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
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  23 months 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
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  23 months 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
»
23 months 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
  • »
    »
    23 months 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
»
23 months 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