| ENG RUS | Timus Online Judge |
Discussion of Problem 1698. Square Country 5roman velichkin PyCharm execution is much faster than here // Problem 1698. Square Country 5 1 Feb 2020 20:13 PyCharm calculates n=2000 in 0.55 sec while here I got exceed time limit with 2.020 sec. I don't get it. Gleb Some tests and hint // Problem 1698. Square Country 5 2 Jun 2018 20:55 n=100: 168 n=555: 984 n=1000: 1785 n=1100: 1963 n=2000: 3598 I solved the equation x(x-1) % 10^i = 0 for every i>1 and i<=n by linear algorithm, using roots for i-1. gnaggnoyil Its solution [4] // Problem 1698. Square Country 5 14 Mar 2009 15:18 The Easy Number is in fact the Automorphic Number. And a number is a Automorphic Number when and only when it is the suffix of another Automorphic Number. So, I download a program to make the Automorphic Number of 2000 dights. And... Gevorgyan Vahan No subject // Problem 1698. Square Country 5 14 Mar 2009 16:59 Edited by author 14.03.2009 22:51 Edited by author 14.03.2009 22:51 Edited by author 14.03.2009 22:51 svr Re: Its solution [1] // Problem 1698. Square Country 5 13 Jul 2009 13:37 It is evident. But how to implement this without long arithmetic. My solution uses Java.BigInteger and reccurence: k^2*10^2*L+k*(2*A-1)*10^L+Z*10^L=Z1*10^L1; where A*A-A=Z*10^L and A1=k*10^L+A- new value where A1*A1-A1=Z1*10^L1, L1>=L+1 unlucky [Vologda SPU] Re: Its solution // Problem 1698. Square Country 5 1 Feb 2010 06:54 Preculc works nice :) invokerj Re: Its solution // Problem 1698. Square Country 5 12 Dec 2013 11:04 well, you win,,,,, DK [Samara SAU 1: X2008] Could 1698 be solved faster than O(N^2) [2] // Problem 1698. Square Country 5 20 Apr 2009 01:07 My solution (without answers precalculation) is about O(N^2). How could it be solved faster? gnaggnoyil Re: Could 1698 be solved faster than O(N^2) [1] // Problem 1698. Square Country 5 5 May 2009 17:22 I wonder the solution within O(n^2) without cheating. Tigran Hakobyan[RAU] Re: Could 1698 be solved faster than O(N^2) // Problem 1698. Square Country 5 19 Jan 2012 00:42 Yes there is. You must solve this mathematically. Solution: Let find all numbers of length 2.Let a is automorphic number then a * (a - 1) = 0(mod 100). Then we know that a and (a - 1) is coprime this fact gives us two cases : 1)a is multiple of 25=> a = 25 * q and (a - 1) is multiple of 4 => a - 1 = 4 * p => 25q - 1=0(mod 4) => 25q = 1(mod 4) then we must find such v s.t. 25 * v = 1 (mod 4), but we know that 4 and 25 coprime => such v exists moreover we can find it use extended Euclid algorithm. In this case v = 1 because 25 * 1 = 1 (mod 4). Then we have (25 * v) * q = 1 * v(mod 4)=> q = 1(mod 4) => q = 1 then a = 25 * q => a = 25-is automorphic number. 2)(a - 1) is multiple of 25 and a is multiple of 4. a = 25q + 1 then use idea described above we find that q = 3 => 25 * 3 + 1=76- is automorphic Using this idea we can find all automorphic numbers which length is <= then given n ! DK [Samara SAU 1: X2008] Fail (compiler) [3] // Problem 1698. Square Country 5 26 Mar 2009 02:25 My solution (about 40K of ifs, 10_26_16_32_J_1516.cpp from petrozadosk archive or I could e-mail it if needed) get this verdict. Are there any restrictions on compilation time? I think they should be added to FAQ Edited by author 26.03.2009 02:26 Vedernikoff Sergey (HSE: АОП) Re: Fail (compiler) [2] // Problem 1698. Square Country 5 26 Mar 2009 15:53 2000 ifs? So inefficient... Better use const int ans[2000] = { 2000 numbers here } DK [Samara SAU 1: X2008] Re: Fail (compiler) [1] // Problem 1698. Square Country 5 26 Mar 2009 18:40 Yes, but sometimes we need a couple of sheets of paper ;) This solution is about 40 pages, and print limit was 50 pages, so... Tolstobrov Anatoliy[Ivanovo SPU] Re: Fail (compiler) // Problem 1698. Square Country 5 27 Aug 2009 22:31 I use only 2 authomorfic numbers with size 2000 and result is count of non zero digits + 1. yuyan What's the answer for N=2000? [1] // Problem 1698. Square Country 5 19 Mar 2009 17:29 Please help. yuyan Re: What's the answer for N=2000? // Problem 1698. Square Country 5 20 Mar 2009 10:23 I know.The answer is 3598. Mansur Wrong answer [1] // Problem 1698. Square Country 5 17 Mar 2009 19:04 В чем ошибка? #include<stdio.h> #include<math.h> void main() { int n,k=0,i=1,j,m; scanf("%d",&n); for(j=1;j<=n;j++) { m=pow(10,j); while (i<m) { if (i*i%m==i) {k++; printf("\n%d %d",i,i*i);} if (i%10==1) i=i+4; else if (i%10==5) i++; else if (i%10==6) i=i+5; } } printf("%d",k); } kis Re: Wrong answer // Problem 1698. Square Country 5 19 Mar 2009 10:42 pow(10, 2000.)? //1 ≤ n ≤ 2000 Maxim Dvoynishnikov (Dnipropetrovsk SU) Leading zeroes [3] // Problem 1698. Square Country 5 14 Mar 2009 13:20 May the numbers contain leading zeroes? Vladimir Yakovlev (USU) Re: Leading zeroes [2] // Problem 1698. Square Country 5 14 Mar 2009 13:46 Easy numbers may not contain leading zeroes Maxim Dvoynishnikov (Dnipropetrovsk SU) Re: Leading zeroes [1] // Problem 1698. Square Country 5 14 Mar 2009 15:00 0625 - correct easy number? gnaggnoyil Re: Leading zeroes // Problem 1698. Square Country 5 15 Mar 2009 07:07 It's a easy number of 3 dights. ddong a problem [1] // Problem 1698. Square Country 5 14 Mar 2009 17:35 whether 125 is a easy-number or not? kis Re: a problem // Problem 1698. Square Country 5 14 Mar 2009 17:55 no(125^2=15 625). 25 is an easy number because 25^2=6 25. 212890625 is an easy number because 212890625^2=45322418 212890625.
|