Prime Divisor of b - Prime Divisor of a

#include <iostream>
using namespace std;
 long long  a,b,t,c,d,k,s,f;

int main ()
{
    c = 1; k = 0;
   cin >>t;
   for (t;t>=1;--t) {
     cin >>a;
      cin >>b;
   if ( b%a==0)
   {
       for( ; d != b; ++c )
       {
         d = a*c;
          if ( b % d == 0)
          {
              k= k+1;
              a = d;
              c = 1;
          }
       }
       cout << k<<"\n";
   }
   else
      cout << "0\n";
   c=1; k=0;
   }
    return 0;

}

Wrong answer on test 4:



#include<iostream>

using namespace std;

//Разложение на простые множители числа n
unsigned long long int PrimeFactorization(unsigned long long n)
{
    unsigned long long int k(0);
    unsigned long long int m = (int)sqrt(n) + 1;

    for (int i(2); i <= m; i++)
    {
        if (n%i == 0)
        {
            while (n%i == 0)

            {
                n /= i;
                k++;
            }
        }
        if (n > 1 && i == m - 1)
        {
            k++;
        }
    }
    return k;
}


int main()
{
    setlocale(LC_ALL, "rus");
    unsigned long long int a, b;
    int n;
    cin >> n;

unsigned long long int* ans = new unsigned long long int[n];

    for (int i(0); i < n; i++)
    {
        cin >> a >> b;
        if ((b%a) == 0)
        {
                ans[i] = PrimeFactorization(b/a) + 1;
        }
        else ans[i] = 0;
    }

    for (int i(0); i < n; i++)
    {
        cout << ans[i] << endl;
    }
    if (n == 0) cout << 0;

    return 0;
}

For two days I can not solve this problem, tell me, please, what is test number 4?

If a=1 then what?
For example
2
1 10
1 20

Can Anyone give me some hints for test 3, I've been working on it for 3 days but still got test 3. I give the right answers for all the tests on forum

".....one could pass from the pub number n to the pub with a number that divides n....."

I think it should be.....

".....one could pass from the pub number n to the pub with a number that is divisible by n"

otherwise it's just wrong....

I have got AC. For test:
1
401 64481201
my AC program answers 2, when the correct answer is 3. Student can drink 3 mugs of ale:
401-160801-64481201

My accepted program gives me :
test 1 :
5
2 6854726
5664 2
2 34
1 5646532
40 1100000
answer :
2
0
2
5
8

/*
 * You should only define the SURC_TEST macros
 * in the compile directives!
 */
#include <stdio.h>

void main(void)
{
    int nT, a, b, nResult;
#ifndef SURC_TEST
    scanf ("%d", &nT);
#else
    nT = 27;
#endif
    for (int iT = 0; iT < nT; ++iT)
    {
#ifndef SURC_TEST
        scanf ("%d %d", &a, &b);
#else
        switch (iT)
        {
        case 0:
            a = 30;
            b = 89;
            break;
        case 1:
            a = 2;
            b = 16;
            break;
        case 2:
            a = 3;
            b = 243;
            break;
        case 3:
            a = 1;
            b = 1;
            break;
        case 4:
            a = 2;
            b = 2;
            break;
        case 5:
            a = 2;
            b = 72;
            break;
        case 6:
            a = 1;
            b = 536870912;
            break;
        case 7:
            a = 1;
            b = 536870912;
            break;
        case 8:
            a = 1;
            b = 214358881;
            break;
        case 9:
            a = 1;
            b = 147008443;
            break;
        case 10:
            a = 1;
            b = 352275361;
            break;
        case 11:
            a = 1;
            b = 28934443;
            break;
        case 12:
            a = 1;
            b = 214921799;
            break;
        case 13:
            a = 1;
            b = 1042441;
            break;
        case 14:
            a = 1;
            b = 2627641;
            break;
        case 15:
            a = 1;
            b = 6086089;
            break;
        case 16:
            a = 1;
            b = 12823561;
            break;
        case 17:
            a = 1;
            b = 24730729;
            break;
        case 18:
            a = 1;
            b = 44930209;
            break;
        case 19:
            a = 1;
            b = 77810041;
            break;
        case 20:
            a = 1;
            b = 129254161;
            break;
        case 21:
            a = 1;
            b = 207561649;
            break;
        case 22:
            a = 1;
            b = 319730161;
            break;
        case 23:
            a = 1;
            b = 480091921;
            break;
        case 24:
            a = 1;
            b = 707081281;
            break;
        case 25:
            a = 1;
            b = 31973;
            break;
        case 26:
            a = 1;
            b = 499999999;
            break;
        default:
            a = 1;
            b = 1;
            break;
        }
#endif
        nResult = 0;
        /********** ALGORITM START ********
         * Insert your algorithm here.
         * input: a, b
         * result write to: nResult
         */

        // ********* ALGIROTM END *********
#ifndef SURC_TEST
        printf ("%d\n", nResult);
#else
        int nRightResult;
        switch (iT)
        {
        case 0:
            nRightResult = 0;
            break;
        case 1:
            nRightResult = 4;
            break;
        case 2:
            nRightResult = 5;
            break;
        case 3:
        case 4:
            nRightResult = 1;
            break;
        case 5:
            nRightResult = 5;
            break;
        case 6:
        case 7:
            nRightResult = 30;
            break;
        case 8:
            nRightResult = 9;
            break;
        case 9:
            nRightResult = 6;
            break;
        case 10:
            nRightResult = 5;
            break;
        case 11:
        case 12:
            nRightResult = 4;
            break;
        case 13:
        case 14:
        case 15:
        case 16:
        case 17:
        case 18:
        case 19:
        case 20:
        case 21:
        case 22:
        case 23:
        case 24:
            nRightResult = 3;
            break;
        case 25:
            nRightResult = 2;
            break;
        case 26:
            nRightResult = 3;
            break;
        default:
            nRightResult = 1;
            break;
        }
        if (nResult == nRightResult)
            printf ("%d\tT\n", iT);
        else
            printf ("%d\tF: %d (should be: %d)\n", iT, nResult, nRightResult);
#endif
    }
}

Edited by author 09.02.2013 22:15

Edited by author 09.02.2013 22:15

ans is amount of prime divisors of b/a+1 (if b mod a=0)
you can try only numbers from 2 to 10^5 and count. if then this n>1 then res++ (because there is a prime > 10^5 and that is only number that we haven't checked). Sorry for my poor English. :)

What is test No. 6 ?

I have to try many times before i solve it.
Now i've got AC 0.001, 246 KB, what I think is a really good job.
It is an easy task but you have to know that if you divide by numbers you should divide only to sqrt;-)

Hi,

Few test cases:

2 846171842
Answer is 3 because 2 * 423085921 = 846171842 and 423085921 is a prime number so can't break it anymore.

Edited by author 01.01.2011 10:39

At the beginning, I write if(a > b)  swap(a, b)， but it got an WA on test 3。。。。

Why do I have access violation on test 3?
There is my cod:

var t,i,j,l:longint;
a,b,s,x:int64;
x1,x2,r:extended;
m,d:array [1..124776567] of int64;
k:array [1..20] of int64;
smena:boolean;

begin
 readln(t);
 for i:=1 to t do
  begin
   readln(a,b);
   if b mod a<>0 then k[i]:=0
    else if a=b then k[i]:=1
    else begin
     x:=round(b/a);
     s:=x;
     l:=0;
     smena:=true;
     j:=1;
     x1:=1;
     x2:=1;
     while (j<100) or (x2-x1>1e-5) do begin
      r:=x2;
      x2:=1/2*(x1+x/x1);
      x1:=r;
      inc(j);
     end;
     j:=3;
     if s mod 2=0 then
      begin
       l:=1;
       d[l]:=2;
       while (s mod 2=0) and (s<>2) do
        begin
         s:=s div 2;
         inc(m[2]);
        end;
      smena:=true;
      end;
     while (s>j) and (j<=round(x2)) do
      if s mod j=0 then
       begin
        if smena then begin smena:=false;inc(l);end;
        d[l]:=j;
        s:=s div j;
        inc(m[j]);
       end
      else begin inc(j,2);smena:=true;end;
     inc(l);
     d[l]:=s;
     inc(m[s]);
     s:=1;
     for j:=1 to l do
      begin
       if m[d[j]]<>0 then s:=s+m[d[j]];
       m[d[j]]:=0;
       d[j]:=0;
      end;
     k[i]:=s;
    end;
  end;
  for i:=1 to t do
   writeln(k[i]);
end.

var i,ans,n:longint; a,b:array[1..1000] of longint;
begin
  readln(n);
  for i:=1 to n do readln(a[i],b[i]);
  for i:=1 to n do
  begin
      if a[i]=1 then
      begin
         if b[i]=1 then writeln(1) else writeln(0);
      end
      else
               begin
      ans:=0;
      while b[i] mod  a[i] =0 do
      begin
        b[i]:=b[i] div a[i];
        inc(ans);
      end;
      writeln(ans);
                end;

  end;
  readln;
end.

I had a stupid mistake just accepted it, hint:
if (a>b) then output 0 :)
Good Luck

Edited by author 29.07.2006 13:12

Student could to drink both 0 or infinity mugs.

Please help me I really can't understand why I've got TLE#3

# include <iostream>
using namespace std;
int main ()
{
    const int prime[3409]={  here prime numbers for 2 to 31699  };
    int i,t,a[25],j,x,y;
    cin>>t;
    for(i=0;i<t;i++)
    {
        cin>>x>>y;
        if(y%x!=0)
        {
            a[i]=0;
            continue;
        }
        y/=x;
        a[i]=1;
        j=0;
        while(y>1)
        {
            if(y%prime[j]==0)
            {
                y/=prime[j];
                a[i]++;
            }
            else
                j++;
        }
    }
    for(i=0;i<t;i++)
        cout<<a[i]<<endl;
    return 0;
}

Edited by author 27.07.2008 02:32