|
|
PyCharm calculates n=2000 in 0.55 sec while here I got exceed time limit with 2.020 sec. I don't get it. 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. 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... Edited by author 14.03.2009 22:51 Edited by author 14.03.2009 22:51 Edited by author 14.03.2009 22:51 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 My solution (without answers precalculation) is about O(N^2). How could it be solved faster? I wonder the solution within O(n^2) without cheating. 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 ! 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 2000 ifs? So inefficient... Better use const int ans[2000] = { 2000 numbers here } Yes, but sometimes we need a couple of sheets of paper ;) This solution is about 40 pages, and print limit was 50 pages, so... I use only 2 authomorfic numbers with size 2000 and result is count of non zero digits + 1. Please help. I know.The answer is 3598. В чем ошибка? #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); } pow(10, 2000.)? //1 ≤ n ≤ 2000 May the numbers contain leading zeroes? Easy numbers may not contain leading zeroes 0625 - correct easy number? It's a easy number of 3 dights. whether 125 is a easy-number or not? 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. |
|
|