number of common divisors

Discuss Computer Science and Programming related problems

Moderators:Labib, bristy1588

HandaramTheGreat
Posts:135
Joined:Thu Dec 09, 2010 12:10 pm
number of common divisors

Unread post by HandaramTheGreat » Thu Feb 10, 2011 7:29 pm

https://www.spoj.pl/problems/COMDIV/

problem statement::
You will be given T (T<=10^6) pair of numbers. All you have to tell is the number of common divisors between two numbers in each pair.
Input

First line of input: T (Number of test cases)
In next T lines, each have one pair A B (0<A,B<=10^6)
Output

One integer describing number of common divisors between two numbers.
Example

Input:

3
100000 100000
12 24
747794 238336



Output:

36
6
2
my code::

Code: Select all

#include<stdio.h>
#include<math.h>
#include<string.h>

int main()
{
    int t, n[5], prime[2][1000], pwr[2][100], i, j, r, s, l, ind, u, v, m, k, sqr, q, mid;
    scanf("%d", &t);
    for(i=1; i<=t; i++)
    {
        q=1;
        scanf("%d %d", &n[0], &n[1]);
        for(j=0; j<2; j++)
        {
            m=0;
            memset(pwr[j], 0, sizeof(pwr[j]));
            sqr=sqrt(n[j]);
            for(k=2; k<=sqr; k++)
            {
                if(!(n[j]%k))
                {
                    prime[j][m]=k;
                    while(!(n[j]%k))
                    {
                        n[j]/=k;
                        pwr[j][m]++;
                    }
                    m++;
                }
                sqr=sqrt(n[j]);
            }
            if(n[j]>1)
            {
                prime[j][m]=n[j];
                pwr[j][m]++;
                m++;
            }
        }
        for(r=0; prime[0][r]; r++)
        {
            ind=1;
            u=0;
            v=m-1;
            while(u<=v && ind)
            {
                mid=(u+v)/2;
                if(prime[0][r]==prime[1][mid])
                {
                    ind=0;
                    if(pwr[1][mid]<pwr[0][r])q*=(pwr[1][mid]+1);
                    else q*=(pwr[0][r]+1);
                }
                else if(prime[0][r]<prime[1][mid])v=mid-1;
                else if(prime[0][r]>prime[1][mid])u=mid+1;
            }
        }
        printf("%d\n", q);
    }
    return 0;
}

i'm getting TLE... how can i improve my code?

abir91
Posts:52
Joined:Sun Dec 19, 2010 11:48 am

Re: number of common divisors

Unread post by abir91 » Thu Feb 10, 2011 11:03 pm

For posts of such kind, please provide a brief description of the main idea of your algorithm and don't post your code unless absolutely necessary (e.g getting wrong answer, well even in that case people usually post ideas because most of the time wrong ideas are the reason for wrong answer). In most of the algorithm related forums, people will not like to decrypt your code to understand what it is doing. But it is tolerable here since you are new :)
Abir

Have you read the Forum Rules and Guidelines?

HandaramTheGreat
Posts:135
Joined:Thu Dec 09, 2010 12:10 pm

Re: number of common divisors

Unread post by HandaramTheGreat » Wed Feb 16, 2011 3:43 pm

sorry... :oops:
here first i've factorized two given number and put the factors in a 2D array 'prime' and the powers in another 2D array 'pwr'... then this algo tries to find common factors between these two lists of factors, if it finds one, then it takes (lower power of the two + 1) as well as multiplies all...
কি লিখসি নিজেই বুঝতেসি না...
if input is
12 24
then first it factorizes them...
$12=2^2 \cdot 3$
$24=2^3 \cdot 3$
factor '2' is common to them, lower power is 2
factor '3' is common to them, lower power is 1
then answer is $(2+1)\cdot(1+1)=6$

User avatar
Zzzz
Posts:172
Joined:Tue Dec 07, 2010 6:28 am
Location:22° 48' 0" N / 89° 33' 0" E

Re: number of common divisors

Unread post by Zzzz » Wed Feb 16, 2011 7:48 pm

আমি জানি না এইটা কাজ করবে কিনা। তবে চেষ্টা করে দেখা যায়। একটা সংখ্যা যদি a,b কে করে তাইলে তাদের gcd কেউ ভাগ করবে। input দেওয়া সংখ্যা ২ টার gcd বের করে তার উৎপাদক সংখ্যা বের করা যায়। এক্ষেত্রে আরকি একটা সংখ্যার prime power factorization করা লাগতিসে, আগে যেখানে ২ টা সংখ্যার করা লাগতো।
gcd বের করতে হইলে এই সূত্রটা ব্যবহার করা যায়: (a,b)=(a%b,b)
For example: (12,18)=(6,12)=(0,6)=6
আর divisibility check করার জন্য বোধহয় (a%b==0) ব্যবহার না করে ((a/b)*b==a) ব্যবহার করলে সময় কম লাগে :?
Every logical solution to a problem has its own beauty.
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)

HandaramTheGreat
Posts:135
Joined:Thu Dec 09, 2010 12:10 pm

Re: number of common divisors

Unread post by HandaramTheGreat » Wed Feb 16, 2011 8:59 pm

হুম, কাজ করল... :)
এখন খেয়াল করলাম, আমি প্রথমে যেইটা করছিলাম, সেইখানেও তো একই কাজই করলাম! খালি খালি ঘুরায়ে-পেঁচায়ে...
প্রথমে রানটাইম হল 4.12s... এরপর (!(a%b)) টা ((a/b)*b==a) তে পাল্টে দিয়ে আসল 4.01... :)
4.01 ও তো অনেক বেশি মনে হইতেসে... Best runtime is 1.05... :o

Post Reply