Prime Divisor of b - Prime Divisor of a lol.hi :)
can be even simpler and faster - Prime Divisors of (b / 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;
} Excuse me but your algo is wrong. input: 5 1 1000000000 1 1000000000 1 1000000000 2 10 2 10 your answer: 19 0 0 2 0 right anse: 19 19 19 2 2 Check it up!.. Press any key to continue . . . 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 I think that the answer should be such: 1 test-10 2 test-20 I was mistaken. I think that the answer should be such: 3 - - - - (1-5-10 ) or (1-2-10) 4 - - - - (1-5-10-20 )or(1-2-10-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 Try this test 1 1 499 999 999 answer is 3. 499 999 999 = 691*723589 The spaces shouldn't be there in the last number by the way. ".....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.... Agreed, was looking if someone else had noticed. Edited by author 22.01.2015 01:28 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 Add one more test: 20 1 536870912 1 536870912 1 214358881 1 147008443 1 352275361 1 28934443 1 214921799 1 1042441 1 2627641 1 6086089 1 12823561 1 24730729 1 44930209 1 77810041 1 129254161 1 207561649 1 319730161 1 480091921 1 707081281 1 31973 Correct answer: 30 30 9 6 5 4 4 3 3 3 3 3 3 3 3 3 3 3 3 2 My Ac program answers: 30 30 9 6 5 4 2 2 2 2 2 2 2 2 2 2 2 2 2 2 Your test is added. If you have more tests, please, send them to timus_support@acm.timus.ru. I don't have any more tests. Edited by author 27.01.2014 18:43 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. :) 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;-) Thanks. I had forgot, that I must divide only to sqrt :) I had TL3) AC now. Edited by author 10.12.2010 01:30 I just counted primes in the factorization of the b/a number. O(sqrt(b/a)), but 0.015 sec. Is a human able to do an AC in 0.001 sec using C language? Even if I got 0.015 sec on the such stupid problems like #1409 and #1000!! 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 I think that for this test case answer is 2 Of course, it is 2. You can't get to the second pub from the second pub. It's pointless. 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.
Your code is wrong. For 2 72 it outputs 3; the solution is 5: 2 -> 4 -> 8 -> 24 -> 72 Edited by author 05.04.2010 06:38 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 Thanks, dude. It was helpful. I say more: if( b%a != 0) then output "0" The case a>b is a particular case of it. Student could to drink both 0 or infinity mugs. he can't drink 0 because and also can't drink infinity mugs. because when he comes to the bar he only drink an ale of beer. count like: test 5 40 5-10-20-40 he drinks 3 ale of beer. Edited by author 29.03.2012 20:32 Drunk student would repeatedly enter pub N (and it divides N) 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 I found all primes less then 100000 (it must be even more than needed) |
|