Блог пользователя ChuVanKhanh

How many solutions does the following equation have for given a b: 1/x+1/y=1/(a*b).
Автор ChuVanKhanh, история, 23 месяца назад, По-английски

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?

  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится

»
23 месяца назад, # |
← Rev. 12   Проголосовать: нравится +19 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    23 месяца назад, # ^ |
      Проголосовать: нравится -15 Проголосовать: не нравится

    i tried using it but it time!

    → Ответить
    • »
      »
      »
      23 месяца назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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

      → Ответить
»
23 месяца назад, # |
← Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

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)$$$.

→ Ответить
  • »
    »
    23 месяца назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      23 месяца назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +28 Проголосовать: не нравится

      thanks for telling me about the optimization!

      → Ответить
      • »
        »
        »
        »
        23 месяца назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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)

        → Ответить
        • »
          »
          »
          »
          »
          23 месяца назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится

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

          → Ответить
          • »
            »
            »
            »
            »
            »
            23 месяца назад, # ^ |
            ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            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$$$.

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              23 месяца назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится 
              #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

              → Ответить
              • »
                »
                »
                »
                »
                »
                »
                »
                23 месяца назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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.

                → Ответить
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  23 месяца назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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?

                  → Ответить
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  23 месяца назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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$$$.

                  → Ответить
»
23 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    23 месяца назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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

    → Ответить
»
23 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 .

→ Ответить