| ENG RUS | Timus Online Judge |
Обсуждение задачи 1118. Нетривиальные числаKUM "i got Ac use 0.02s" i used this solution but in JAVA [2] // Задача 1118. Нетривиальные числа 25 мар 2008 18:18 public static void main(String[] args){ Scanner in = new Scanner(System.in); int k,ans=0,start,stop; double r; boolean p; start=in.nextInt(); stop=in.nextInt(); r=2147483647; if (start==1) System.out.println(1); else { for (int i=stop; i>=start; i-- ){ p=true; for (int j=2; j<=Math.round(Math.sqrt(i)); j++) { if ((i % j)==0) { p=false; break; } } if (p) { ans=i; r=1/i; break; } } for (int i=stop; i>=start; i--){ if (Math.abs(Math.sqrt(i)-Math.round(Math.sqrt(i)))<(1e-8)) { if (r>(1+Math.sqrt(i))/i) ans=i; break; } } if (ans!=0) { System.out.println(ans); } else { for (int i=start; i<=stop; i++){ k=1; for (int j=2; j<=Math.round(Math.sqrt(i)); j++) { if ((i % j)==0) { k+=(j+(i / j)); if (j==(i / j)) k-=j; } if (r>(k/i)) { ans=i; r=k/i; } } } System.out.println(ans); } } } Where is my mistake& Edited by author 25.03.2008 18:19 Meni Packeou No subject [1] // Задача 1118. Нетривиальные числа 17 авг 2008 23:04 Edited by author 18.08.2008 14:34 Meni Packeou Re: "i got Ac use 0.02s" i used this solution but in JAVA // Задача 1118. Нетривиальные числа 18 авг 2008 14:33 rohit WA#8 [1] // Задача 1118. Нетривиальные числа 28 май 2008 02:47 Please tell me what test it is. Howard Liu Re: WA#8 // Задача 1118. Нетривиальные числа 29 май 2008 11:15 Just precompute a bunch of answers in a safe way. Then for sure you won't get WA. Rustam wa9. help please // Задача 1118. Нетривиальные числа 24 апр 2008 17:42 here is my code. what's wrong with my program?please give me some tests. thx program z1118_1; {$APPTYPE CONSOLE} uses SysUtils; var i,n:longint; k:longint; function simple(n:longint):boolean; var i:longint; begin result:=true; if n=2 then exit; result:=false; for i:=2 to trunc(sqrt(n)) do if n mod i=0 then exit; result:=true; end; begin read(n,k); if k>n then begin i:=k; k:=n; n:=i; end; if (n<=1) and (k>=1) then begin write(1); halt(0); end; if n=k then begin write(k); halt(0); end; for i:=k downto n do if simple(i) then begin write(i); halt(0); end; for i:=n to k do if i mod 2=1 then begin write(i); halt(0); end; halt(0); end. bbs.hasea.com Why CE!?Help me!I have comiled it in my computer!!! [2] // Задача 1118. Нетривиальные числа 13 сен 2007 17:10 #include <iostream> #include <math.h> using namespace std; long long a,b; long long i,j; long long sum,maxi; double s; double maxn; int main () { cin>>a>>b; maxn=100000; for (i=a;i<=b;i++) { sum=1; for (j=2;j<sqrt(i);j++) if (i%j==0) sum=sum+j+i/j; if (((long long)(sqrt(i)))*((long long)(sqrt(i)))==i) sum=sum+(long long)(sqrt(i)); s=(double)sum/i; if (s<maxn) { maxn=s; maxi=i; } } cout<<maxi<<endl; return (0); } Edited by author 13.09.2007 17:13 Alias (Alexander Prudaev) Re: Why CE!?Help me!I have comiled it in my computer!!! [1] // Задача 1118. Нетривиальные числа 13 сен 2007 20:04 try to overload function "sqrt" for "long long" long long sqrt(long long x) { return (long long)sqrt((double) x); } by the way you must to use "__int64" instead of "long long" you can use option "Reply" when submit your solution To this E-Mail address your@email.adress and you have got such a message: You tried to solve problem 1118 Nontrivial numbers. Your solution was compiled with the following errors: 641078b2-a88c-43db-be02-6b6e5e5dd8fc 641078b2-a88c-43db-be02-6b6e5e5dd8fc(21): error: more than one instance of overloaded function "sqrt" matches the argument list: function "sqrt(double)" function "sqrt(float)" function "sqrt(long double)" argument types are: (__int64) for (j=2;j<sqrt(i);j++) ^ 641078b2-a88c-43db-be02-6b6e5e5dd8fc(23): error: more than one instance of overloaded function "sqrt" matches the argument list: function "sqrt(double)" function "sqrt(float)" function "sqrt(long double)" argument types are: (__int64) if (((long long)(sqrt(i)))*((long long)(sqrt(i)))==i) sum=sum+(long long)(sqrt(i)); ^ 641078b2-a88c-43db-be02-6b6e5e5dd8fc(23): error: more than one instance of overloaded function "sqrt" matches the argument list: function "sqrt(double)" function "sqrt(float)" function "sqrt(long double)" argument types are: (__int64) if (((long long)(sqrt(i)))*((long long)(sqrt(i)))==i) sum=sum+(long long)(sqrt(i)); ^ 641078b2-a88c-43db-be02-6b6e5e5dd8fc(23): error: more than one instance of overloaded function "sqrt" matches the argument list: function "sqrt(double)" function "sqrt(float)" function "sqrt(long double)" argument types are: (__int64) if (((long long)(sqrt(i)))*((long long)(sqrt(i)))==i) sum=sum+(long long)(sqrt(i)); ^ 641078b2-a88c-43db-be02-6b6e5e5dd8fc(32): warning #1: last line of file ends without a newline } ^ compilation aborted for 641078b2-a88c-43db-be02-6b6e5e5dd8fc (code 2) bbs.hasea.com Re: Why CE!?Help me!I have comiled it in my computer!!! // Задача 1118. Нетривиальные числа 14 сен 2007 16:50 I see,and I've AC it Nash help me please // Задача 1118. Нетривиальные числа 8 июл 2007 00:27 Help me please in my problem 1118 My code: #include <stdio.h> #pragma comment(linker, "/STACK:16777216") int a,b,c,i,k,n,j; float min = 6555,d; void main() { scanf("%d",&a); scanf("%d",&b); for(i=a;i<=b;i++) { {n=0; for(k=1;k<=b/2;k++) { {if(i%k==0) { n=n+k; } } } d=(float)n/i; if (d<min) { min=d; j=i; } } printf("%d",j); } } I have Time limit exceeded. I need optimal solution of this task. Help me please! my @ is nash88@mail.ru Edited by author 08.07.2007 00:28 Edited by author 08.07.2007 00:28 serendipity seems no one has problem with the time limit !!! :( [1] // Задача 1118. Нетривиальные числа 31 июл 2006 14:32 what is the fastest way to find the divisors of a number? shrek Re: seems no one has problem with the time limit !!! :( // Задача 1118. Нетривиальные числа 2 ноя 2006 12:37 consider the bigest prime number in the given range. Grab a bit incorrect task [4] // Задача 1118. Нетривиальные числа 10 фев 2006 12:06 In the task of problem #1118 the triviality(1) was not defined. test #4 has 1 as i. after putting triviality(1) be equal to 0, i've gotten AC. So, in my opinion, this moment should be fixed in the task. P.S. sorry for my bad English Ayhan Aliyev [BOTL] Re: a bit incorrect task [3] // Задача 1118. Нетривиальные числа 10 фев 2006 13:12 Yes I agree with you. Problem definition is unclear. Vladimir Yakovlev (USU) Re: a bit incorrect task [2] // Задача 1118. Нетривиальные числа 10 фев 2006 14:12 Citation from problem statement: Recall that a proper divisor of a natural number is the divisor that is strictly less than the number. So, 1 has no proper divisors and its sum equals to 0. Hence, triviality of 1 equals to 0.Grab Re: a bit incorrect task [1] // Задача 1118. Нетривиальные числа 10 фев 2006 19:59 Vladimir Yakovlev (USU) писал(a) 10 февраля 2006 14:12 Citation from problem statement: Recall that a proper divisor of a natural number is the divisor that is strictly less than the number. So, 1 has no proper divisors and its sum equals to 0. Hence, triviality of 1 equals to 0.Sorry, but I do not agree with you. 0 is less then 1, but it is not its divisor. So, we have a sutuation: there's NO divisor (that's why the sum is not 0, but it doesn't exist), strictly the function doesn't have any value at 1 (т.е. функция не определена в точке 1), but nil is a number and the condition Triv(1)=0 means it has it! that what wanted to say. P.S. sorry for using Russian, but I really do not know how to explain my think in English Edited by author 10.02.2006 20:00 Edited by author 10.02.2006 20:20 Vladimir Yakovlev (USU) Re: a bit incorrect task // Задача 1118. Нетривиальные числа 11 фев 2006 03:23 In maths the sum of empty set of numbers is traditionally considered to be equal to zero. Tony I have got AC in this problem.But I want to know the best way to solve this problem.Could somebody help?? [3] // Задача 1118. Нетривиальные числа 8 май 2003 17:48 turalSatol Re: I have got AC in this problem.But I want to know the best way to solve this problem.Could somebody help?? [2] // Задача 1118. Нетривиальные числа 21 янв 2006 18:25 very good learn botl_ayhan Solve it like a man! [1] // Задача 1118. Нетривиальные числа 23 янв 2006 13:08 At least Tony solves it like a man, not by copy-pasting source code from forum!!! Like you. BOTLMahir Re: Solve it like a man! // Задача 1118. Нетривиальные числа 27 янв 2006 00:46 I agree with you and all users mustn't write AC PROGRAM. PLEASEEEEEEEEEEEE SSS That ****en WA#3 Again and again!!! Please give me some tests // Задача 1118. Нетривиальные числа 20 янв 2006 20:04 A tried a lot but wa#3 always shown! I find the largest prime in the range, If there isnt so I just use brute force. I know that triviality(1)=0 ... but Why WA??? const a:array[1..168] of longint=( 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71, 73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167 ,173, 179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271 ,277,281, 283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397 ,401,409, 419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521 ,523,541, 547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647 ,653,659, 661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787 ,797,809, 811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929 ,937,941,947,953,967,971,977,983,991,997); var m,n,minn,i,k:longint; y,min:real; function prime(x:longint):boolean; var j:longint; begin for j:=1 to 168 do begin if a[j]>trunc(sqrt(x)) then begin prime:=true; exit; end; if x mod a[j]=0 then begin prime:=false; exit; end; end; end; function count(x:longint):longint; var s,i:longint; begin s:=1; for i:=2 to x-1 do if x mod i=0 then s:=s+i; count:=s; end; begin readln(n,m); if (n=1) or (m=1) then begin writeln(1); halt; end; if n=m then begin writeln(n); halt; end; for i:=m downto n do if prime(i) then begin writeln(i); halt; end; min:=2147483647; for i:=n to m do begin y:=count(i)/i; if y<min then begin min:=y; minn:=i; end; end; writeln(minn); end. michel mizrahi WHY WA on 1118!!!!!!! [1] // Задача 1118. Нетривиальные числа 4 апр 2005 05:10 I get too many WA with this problem (1118). In test number 3 I just use a simple algorithm, if lower number is 1 then print 1 else go in a loop from j to l, I mean from the max number until the min. number and start to calculate the nontrivial number of every number until I find a prime, if I find a prime then I print the least nontrivial number until this number (including the first prime that I found) here is my code: #include <stdio.h> #include <math.h> double s,res=2147483647; int r=1,rs; calc(int n,int p){ int i,k=1; p++; for(i=0;i<p;i++) k*=n; k=(k-1)/(n-1); r*=k; } fact(int n){ int p=0,i=3,l=sqrt(n)+1; double t=n; while(n%2==0){ n/=2; p++; } if(p>0){ calc(2,p); p=0; } while(i<l){ while(n%i==0){ n/=i; p++; } if(p>0){ calc(i,p); p=0; } i+=2; } if(n>1) calc(n,1); r-=t; s=r/t; if(s<res){ rs=t; res=s; } r=1; } is_prime(n){ int i=3,l=sqrt(n)+1; if(n%2==0) return 0; for(i=3;i<l;i+=2) if(n%i==0) return 0; return 1; } int main(){ int l,i,j; scanf("%d %d",&l,&j); if(l==1) printf("1\n"); else{ for(i=j;i>=l;i--) { fact(i); if(is_prime(i)) break; } printf("%d",rs,res); } return 0; } if someone can help me I would appreciate very much!! thanks Cybernetics Team Re: WHY WA on 1118!!!!!!! // Задача 1118. Нетривиальные числа 4 апр 2005 14:38 I search the greatest prime in the interval. If there are not any primes then we go brute force kkgz i have seen the ac pro of pas,but i use c++ but can't got AC,any master can help me ? [2] // Задача 1118. Нетривиальные числа 21 апр 2004 08:50 #include<iostream.h> #include<math.h> #include<limits.h> main() { long D,U,i,sum,crno,minN,j; double min,ratio,nouse; int flag=0; cin>>D>>U; min=1000000; minN=D; for(long t=1000000;t>=2;t--) { U=t; if(D==1) cout<<'0'; else { for(i=U;i>=D;i--) { sum=1; for(j=2;j<=sqrt((double)i);j++) { if(i%j==0) { sum+=j+i/j; } } if(i%(j-1)==0) sum-=j; ratio=double(sum)/(double)i; if(ratio<=min) { min=ratio; minN=i; if(sum==1) { for(long k=U;k>=D;k--) { if(modf(sqrt((double)k),&nouse)==0) { ratio=(1+sqrt((double)k))/(double)k; if(ratio>min) break; else { min=k; minN=k; break; } } } break; } } } cout<<minN; } } } Gheorghe Stefan Re: i have seen the ac pro of pas,but i use c++ but can't got AC,any master can help me ? [1] // Задача 1118. Нетривиальные числа 22 апр 2004 16:57 if there are prime numbers in the interval you should print it. Else, if there are not primes in the interval, it is quite small and you can brute search the number. If the first bound of the interval is 1 you must print 1 (I got many WAs not knowing this). Evil Cheater Re: i have seen the ac pro of pas,but i use c++ but can't got AC,any master can help me ? // Задача 1118. Нетривиальные числа 28 апр 2004 09:51 I'm doing exactly that but I keep getting WA. Could you give me some sample inputs/outputs? vongman How could somebody get AC in 0.01 sec !!! [2] // Задача 1118. Нетривиальные числа 22 апр 2003 14:51 How could somebody get AC in 0.01 sec !!! and uses mem lower than 50K plz. show your algorithm Pasha 0.01 and 24KB (+) [1] // Задача 1118. Нетривиальные числа 22 апр 2003 16:28 it is a part of my Ac prog... I`ve cut others and also did a little changes to avoid letting someone Copy It: Aidin_n7@hotmail.com ~~~~~~~~~~~~~~~~~ for i:=b downto a do begin p:=1; for j:=2 to trunc(sqrt(i)) do if (i mod j)=0 then begin p:=p+j+(i div j); if sqr(trunc(sqrt(i)))=i then p:=p-trunc(sqrt(i)); if p>i*m then begin p:=-1; break; end; end; if p=1 then begin writeln(i); readln; halt; end else if (p>0) and (p/i<m) then begin m:=p/i; ans:=i; end; ~~~~~~~~~~~~~~~~~ Best Aidin vongman Re: 0.01 and 24KB (+) // Задача 1118. Нетривиальные числа 23 апр 2003 10:38 Don't worry. I got AC before I want to know the best solution. Thank you for your help. Koala Why I have got WA? // Задача 1118. Нетривиальные числа 26 май 2002 19:29 This is my program. I will really appreciate your help. program nontrivial; var m,n,i,j,k,s,mi:longint; min:real; begin readln(m,n); min:=1e+10; mi:=0; for k:=n downto m do begin s:=0; for j:=1 to k-1 do if k mod j=0 then inc(s,j); if s=1 then begin writeln(k); halt end; if s/k<min then begin min:=s/k; mi:=k end; end; writeln(mi); end. I am david. Tabo. WHI I GOT Time Limit Exceeded. HERE IS A MY PRIGRAM. THENKS [1] // Задача 1118. Нетривиальные числа 24 май 2002 13:31 var sol,gam,i,j,k,m,n:longint; min,min1:real; procedure readdata; begin readln (n,m); end; procedure solve; begin min:=n; if n=1 then begin writeln (1); halt; end; min1:=m; for i:=n to m do begin k:=i div 2; for j:=2 to k do if i mod j = 0 then gam:=gam+j; min:=gam/i; if min1>min then begin sol:=i; min1:=min; end; gam:=1; end; end; procedure print; begin writeln (sol); end; begin readdata; solve; print; end. raxtinhac Re: WHI I GOT Time Limit Exceeded. HERE IS A MY PRIGRAM. THENKS // Задача 1118. Нетривиальные числа 24 май 2002 13:41 try this test 1 1000000 => time limit of course O( n * (n + 1) / 4 ) => too big. Thinhk more little , you will find something interesting. Good luck M.Si Why I get WA? Help me PLS!!! // Задача 1118. Нетривиальные числа 24 май 2002 12:58 {$N+} var t1,t2:extended; num,i,j,k,divisor:longint; s:string; function triv(n:longint):extended; var i,j, counter:longint; begin j:=round(sqrt(n)); counter:=0; divisor:=0; for i:=1 to j do if n mod i=0 then begin inc(counter,i); inc(divisor); end; if counter>1 then for i:=j+1 to n div 2 do if n mod i =0 then begin inc(counter,i); inc(divisor); end; triv:=counter/n; end; procedure die(s:string); begin writeln(s); halt(0); end; begin writeln('Input I and J'); read(i,j); if i<=0 then die('wrong input'); if j>=1000000 then die('wrong input'); if i=j then begin str(i,s); die(s); end; if i=1 then begin str(1,s); die(s); end; t1:=maxlongint; for k:=j downto i do begin t2:=triv(k); if t2<t1 then begin t1:=t2; num:=k; if divisor=1 then begin str(k,s); die(s) end; end; end; writeln(num); end. qwt Why I got wrong? // Задача 1118. Нетривиальные числа 7 май 2002 09:17 const ss:array[1..169] of longint=( 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71, 73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167 ,173, 179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,27 1,277,281, 283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,39 7,401,409, 419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,52 1,523,541, 547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,64 7,653,659, 661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,78 7,797,809, 811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,92 9,937,941, 947,953,967,971,977,983,991,997,0); var a:array[1..169] of longint; i,j,k,x,y:longint; function judge(m:longint):boolean; var i,j,k,n,q:longint; begin n:=m; fillchar(a,sizeof(a),0); judge:=false; i:=1; while (n>1)and(i<169) do begin while n mod ss[i]=0 do begin inc(a[i]); n:=n div ss[i]; end; inc(i); end; if n>1 then begin ss[169]:=n;a[169]:=1;end; k:=1; for i:=1 to 169 do if a[i]>0 then begin q:=1; for j:=1 to a[i] do q:=q*ss[i]+1; if m*2<k*q then exit; k:=k*q; end; judge:=true; end; begin readln(x,y); for i:=x to y do if judge(i) then begin writeln(i);break;end; end. qwt why i got wrong answer? // Задача 1118. Нетривиальные числа 28 апр 2002 19:30 var z,y,x,a,b,tt,i,j,k,p,q,r:longint; ss:array[1..10000] of longint; s:string; begin tt:=1;ss[1]:=2; for i:=3 to trunc(sqrt(1000000)) do begin for j:=1 to tt do if (i mod ss[j]=0)or(ss[j]>trunc(sqrt(i))) then break; if i mod ss[j]<>0 then begin inc(tt); ss[tt]:=i; end; end; readln(a,b); for y:=a to b do begin q:=1; x:=y; r:=1; k:=1; while (x<>1 )and(k<>tt) do begin for j:=k to tt do if x mod ss[j]=0 then break; k:=j; if x mod ss[j]=0 then begin z:=1; p:=1; while x mod ss[j]=0 do begin z:=z*ss[j]; p:=z+p; q:=q*ss[j]; x:=x div ss[j]; end; r:=r*p; if (r>=2*q) then break; end; end; if x<>1 then begin r:=r*(x+1);q:=y;end; if r<2*q then begin writeln(y); halt; end; end; end. I am david. Tabo. help me pleas??? i can not get AC!! // Задача 1118. Нетривиальные числа 19 апр 2002 00:41 type c=record d:longint; h:real; end; var sol,gam,i,j,k,l,m,n,b:longint; a:array [1..10000] of c; min:real; procedure readdata; begin readln (n,m); end; procedure check; begin if n=1 then begin writeln (0); halt; end; end; procedure solve; begin for i:=n to m do begin k:=i div 2; for j:=1 to k do if i mod j = 0 then gam:=gam+j; inc (b); a[b].d:=i; a[b].h:=gam/i; gam:=0; if i>=m then break; end; min:=a[1].h; for i:=1 to b do if min>a[i].h then begin min:=a[i].h; sol:=a[i].d; end; end; procedure print; begin writeln (sol); end; begin readdata; check; solve; print; end. nedio nonetrivialnumbers [1] // Задача 1118. Нетривиальные числа 24 янв 2002 21:25 what exactly means this problem (Nonetrivial numbers1118): 1.to find the smallest trivial number or 2.to find the number in the input range that have the smallest trivialaty? if it is 1 then what is trivial number??? Miguel Angel The task is(+) // Задача 1118. Нетривиальные числа 24 янв 2002 23:00 To find the SMALLEST number IN the input range that have the SMALLEST trivialaty? And the problem of almost everyone. Triviality(1) = 0 Luck :) Badd Can I use loop from biger number to less number until find the prime number, else print the least trivial number that find. How is the input to make me wrong answer??? [1] // Задача 1118. Нетривиальные числа 28 дек 2001 20:49 shitty.Mishka A hint (+) // Задача 1118. Нетривиальные числа 28 дек 2001 21:56 Maybe you didn't think of those cases where lower number is 1? For any test like this: 1 k The answer of your program should be 1. Hope this will help. Good luck!
|