Can somebody tell me how solve this problem? what is test19? maybe some wrong in test19 It can be solved using backtracking :) can anyone tell me what algo for this problem > can anyone tell me what algo for this problem I can, though my approach wasn't so easy. I used precalculations. My way is to generate all pairs (N, P), where P = 1, 2, ... - complexity of number and N - such minimal number, that has exactly P divisors. How to do this with such large inputs? Solve another problem: recover N, if you know P. I used backtrack there, but still I'm wondering whether there is a more beautiful way. First I wrote a recursive function that tries all v=2^a * 3^b * 5^c * 7^d * 11^e * ... with a>=b>=c>=... It generates +- a million possibilities and takes around 300 ms for each case. So I got TLE with 100 cases. Then I wrote code that reads all the n values and sort them. Then I call the recursive function with 10^18. I added a binary search to it that finds the smallest n greater or equal to v and update the best result for it. When the recursive function returns, I update the results for the larger values of n with the smaller results. And then I output the results in the same order as the input. All in less that 50 lines of C++. I think u can safely assume that that there is no number with power>10 so 10>=a>=b>=c>=d... and now I think u will get AC without doing anything else. Plus small small optimisation.. like breaking at a point if current no. > query(which is obvious to do so) and other such small small optimisation will do. Other thing is to check if ur current no. doesnt exceed the long long range (u can only check by using log()...) Баур, эта задача решатся "в лоб" had wa on test 17, changed long long to long double and calculated everything until 1e20 and got accepted. I precalculated this numbers by algo like bfs, the last most complex numbers have 92160, 96768, 98304, 103680 divisors. Wa17 - max test. I have wa17 because of wrong right border in binary search. Check your program, may be it hepls you. Also you can visit https://oeis.org/A002182Same code gets AC in c++ but gets TLE in test 14 in Java. Turns out, even if you dont use the condition of "powers of primes should be in non increasing order" , your c++ code gets AC, while for Java you have to use that condition. Edited by author 25.04.2018 06:42 Edited by author 25.04.2018 06:42 Use cin cout for c++ Edited by author 29.10.2013 13:59 thx for your help or I will be insane. try: 1 897612484786617600 answer: 897612484786617600 103680 #include<stdio.h> #include<math.h> #include<map> using namespace std; map<unsigned long long,int> M;
int Prime[30]={0,2,3,5,7},Pct=5; void genprime(int); int expP[30]={70},solVal[500],ctsol; unsigned long long solKey[500]; void gensol(unsigned long long,int); void arrange(); main() { genprime(30); gensol(1,1); arrange(); //for (int i=1;i<=ctsol;i++) printf("%lld %d\n",solKey[i],solVal[i]); int Test,id; unsigned long long n; scanf("%d",&Test); for (int t=1;t<=Test;t++) { scanf("%llu",&n); id=ctsol; while (solKey[id]>n) id--; printf("%llu %d\n",solKey[id],solVal[id]); } } void genprime(int K) { int i,j; for (i=11;Pct<K;i+=2) { for (j=1;Prime[j]*Prime[j]<=i;j++) if (i%Prime[j]==0) break; if (Prime[j]*Prime[j]>i) Prime[Pct++]=i; } //for (int i=1;i<Pct;i++) printf("%d\t",Prime[i]); } void gensol(unsigned long long x,int pID) { int i,pro=1; for (i=1;i<30;i++) pro*=expP[i]+1; M[x]=pro;
if (log10(x)+log10(Prime[pID])<=18.3 && expP[pID]<expP[pID-1]) { expP[pID]++; gensol(x*Prime[pID],pID); expP[pID]--; } if (log10(x)+log10(Prime[pID+1])<=18.3 && expP[pID]!=0) { expP[pID+1]++; gensol(x*Prime[pID+1],pID+1); expP[pID+1]--; } } void arrange() { map<unsigned long long,int>::iterator it; for (it=M.begin();it!=M.end();it++) { if (it->second > solVal[ctsol]) { ctsol++; solKey[ctsol]=it->first; solVal[ctsol]=it->second; } } } Don't know why. Maybe something tricky between 1e11 ~ 1e12? The same problem. Even precalculated data didn't help Wrong answer 3 test. Help! In my case it was problems with test 1 12 Correct answer 12 6 Edited by author 22.07.2011 18:01 try 2 12 2 Second test number is smaller than the first really curious about it, do you have any idea? Am I right? 19 1 1 1 10 6 4 100 60 12 1000 840 32 10000 7560 64 100000 83160 128 1000000 720720 240 10000000 8648640 448 100000000 73513440 768 1000000000 735134400 1344 10000000000 6983776800 2304 100000000000 97772875200 4032 1000000000000 963761198400 6720 10000000000000 9316358251200 10752 100000000000000 97821761637600 17280 1000000000000000 866421317361600 26880 10000000000000000 8086598962041600 41472 100000000000000000 74801040398884800 64512 1000000000000000000 856811873911587456 491520 No, for 10^18 correct answer is 897612484786617600 103680 Big thanks! :) Try using unsigned long long and compute the numbers untill 10^19 WA 8 #include <iostream> #include <math.h> using namespace std; long long h[104680]; int main(){ int wr,a2,a3,a5,a7,a11,a13,a17,a19,a23,a29,a31,a37,i,t; long long p,u,f1,c1,e,k,n,g,c,f,b2,b3,b5,b7,b11,b13,b17,b19,b23,b29,b31,b37,j; for (i=1;i<=104000;i++)h[i]=1000000000000000011; for (a2=0;a2<=8;a2++){ b2=powf(2,a2); for (a3=0;a3<=4;a3++){ if (a2<a3)break; b3=b2*powf(3,a3); for (a5=0;a5<=3;a5++){ if (a2<a5)break; b5=b3*powf(5,a5); for (a7=0;a7<=2;a7++){ if (a2<a7)break; b7=b5*powf(7,a7); for (a11=0;a11<=1;a11++){ if (a2<a11)break; b11=b7*powf(11,a11); for (a13=0;a13<=1;a13++){ if (a2<a13)break; b13=b11*powf(13,a13); for (a17=0;a17<=1;a17++){ if (a2<a17)break; b17=b13*powf(17,a17); for (a19=0;a19<=1;a19++){ if (a2<a19)break; b19=b17*powf(19,a19); for (a23=0;a23<=1;a23++){ if (a2<a23)break; b23=b19*powf(23,a23); for (a29=0;a29<=1;a29++){ if (a2<a29)break; b29=b23*powf(29,a29); for (a31=0;a31<=1;a31++){ if (a2<a31)break; b31=b29*powf(31,a31); for (a37=0;a37<=1;a37++){ k=b31*powf(37,a37); g=(a2+1)*(a3+1)*(a5+1)*(a7+1)*(a11+1)*(a13+1); g=g*(a17+1)*(a19+1)*(a23+1)*(a29+1)*(a31+1)*(a37+1); if (g<=103680){ if ((0<k)&&(k<h[g])){ h[g]=k; } } } } } } } } } } } } } } cin >> t; for (i=1;i<=t;i++){ cin >> n; f1=0;c1=0; for (j=1;j<=103680;j++){ if (h[j]<=n){ f1=h[j]; c1=j; } } cout << f1 << " " << c1 << endl; } cin >> i; return 0; } WA 11 #include <iostream> #include <math.h> //#include <fstream> //#include <ctime> using namespace std; int main(){ int a2,a3,a5,a7,a11,a13,a17,a19,a23,a29,a31,a37,i,t; long long k,n,g,c,f,b2,b3,b5,b7,b11,b13,b17,b19,b23,b29,b31,b37; //ifstream f1("1.txt"); cin >> t;//clock_t t0 = clock(); for (i=1;i<=t;i++){ cin >> n; c=1; f=1; if (n>1000000000000){ for (a2=4;a2<=9;a2++){ b2=powf(2,a2); for (a3=1;a3<=5;a3++){ if (a2<a3)break; b3=b2*powf(3,a3); for (a5=1;a5<=4;a5++){ if (a2<a5)break; b5=b3*powf(5,a5); for (a7=1;a7<=3;a7++){ if (a2<a7)break; b7=b5*powf(7,a7); for (a11=1;a11<=2;a11++){ if (a2<a11)break; b11=b7*powf(11,a11); for (a13=0;a13<=1;a13++){ if (a2<a13)break; b13=b11*powf(13,a13); for (a17=0;a17<=1;a17++){ if (a2<a17)break; b17=b13*powf(17,a17); for (a19=0;a19<=1;a19++){ if (a2<a19)break; b19=b17*powf(19,a19); for (a23=0;a23<=1;a23++){ if (a2<a23)break; b23=b19*powf(23,a23); for (a29=0;a29<=1;a29++){ if (a2<a29)break; b29=b23*powf(29,a29); for (a31=0;a31<=1;a31++){ if (a2<a31)break; b31=b29*powf(31,a31); for (a37=0;a37<=1;a37++){ k=b31*powf(37,a37); g=(a2+1)*(a3+1)*(a5+1)*(a7+1)*(a11+1)*(a13+1); g=g*(a17+1)*(a19+1)*(a23+1)*(a29+1)*(a31+1)*(a37+1); if ((((k<=n) && (c<g))||((k<f) && (c==g)))&&(k>0)){ c=g; f=k; } } } } } } } } } } } //lkj3:; } } cout << f << " " << c << endl; } else { if (n>1000000){ for (a2=2;a2<=8;a2++){ b2=powf(2,a2); for (a3=1;a3<=4;a3++){ if (a2<a3)break; b3=b2*powf(3,a3); for (a5=1;a5<=3;a5++){ if (a2<a5)break; b5=b3*powf(5,a5); for (a7=0;a7<=2;a7++){ if (a2<a7)break; b7=b5*powf(7,a7); for (a11=0;a11<=1;a11++){ if (a2<a11)break; b11=b7*powf(11,a11); for (a13=0;a13<=1;a13++){ if (a2<a13)break; b13=b11*powf(13,a13); for (a17=0;a17<=1;a17++){ if (a2<a17)break; b17=b13*powf(17,a17); for (a19=0;a19<=1;a19++){ if (a2<a19)break; b19=b17*powf(19,a19); for (a23=0;a23<=1;a23++){ if (a2<a23)break; b23=b19*powf(23,a23); for (a29=0;a29<=1;a29++){ if (a2<a29)break; b29=b23*powf(29,a29); for (a31=0;a31<=1;a31++){ if (a2<a31)break; k=b29*powf(31,a31); g=(a2+1)*(a3+1)*(a5+1)*(a7+1)*(a11+1)*(a13+1); g=g*(a17+1)*(a19+1)*(a23+1)*(a29+1)*(a31+1); if (((k<=n) && (c<g))||((k<f) && (c==g))){ c=g; f=k; } } } } } } } } } } //lkj3:; }
} cout << f << " " << c << endl; } else { for (a2=0;a2<=7;a2++){ b2=powf(2,a2); for (a3=0;a3<=4;a3++){ if (a2<a3)break; b3=b2*powf(3,a3); for (a5=0;a5<=2;a5++){ if (a2<a5)break; b5=b3*powf(5,a5); for (a7=0;a7<=2;a7++){ if (a2<a7)break; b7=b5*powf(7,a7); for (a11=0;a11<=1;a11++){ if (a2<a11)break; b11=b7*powf(11,a11); for (a13=0;a13<=1;a13++){ if (a2<a13)break; b13=b11*powf(13,a13); for (a17=0;a17<=1;a17++){ if (a2<a17)break; k=b13*powf(17,a17); g=(a2+1)*(a3+1)*(a5+1)*(a7+1)*(a11+1)*(a13+1); g=g*(a17+1); if (((k<=n) && (c<g))||((k<f) && (c==g))){ c=g; f=k; } } } } } } //lkj3:; }
} cout << f << " " << c << endl; } }
}//clock_t t1 = clock();cout << "time: " << (double)(t1 - t0) / CLOCKS_PER_SEC << endl; cin >> i; return 0; } Solved 15 hours!!!!!!!!!!!!!!!!!!!!!!!! long long < 2^63 Received overflow On it received WA!!!!!!!!! Edited by author 10.07.2011 23:16 Edited by author 10.07.2011 23:17 Edited by author 10.07.2011 23:17 Edited by author 10.07.2011 23:17 maybe some wrong in test19 I also keep getting WA on test 19..did you arrive at anything regarding this ? |
|