| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| PyCharm execution is much faster than here | roman velichkin | 1698. Квадратная страна 5 | 1 фев 2020 20:13 | 1 |
PyCharm calculates n=2000 in 0.55 sec while here I got exceed time limit with 2.020 sec. I don't get it. |
| Some tests and hint | Gleb Koveshnikov | 1698. Квадратная страна 5 | 2 июн 2018 20:55 | 1 |
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. |
| Its solution | gnaggnoyil | 1698. Квадратная страна 5 | 12 дек 2013 11:04 | 5 |
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 |
| Could 1698 be solved faster than O(N^2) | DK [anonymous] | 1698. Квадратная страна 5 | 19 янв 2012 00:42 | 3 |
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 ! |
| Fail (compiler) | DK [anonymous] | 1698. Квадратная страна 5 | 27 авг 2009 22:31 | 4 |
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. |
| What's the answer for N=2000? | Arthas | 1698. Квадратная страна 5 | 20 мар 2009 10:23 | 2 |
I know.The answer is 3598. |
| Wrong answer | Mex-Mans | 1698. Квадратная страна 5 | 19 мар 2009 10:42 | 2 |
В чем ошибка?
#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 |
| Leading zeroes | Maxim Dvoynishnikov (Dnipropetrovsk NU) | 1698. Квадратная страна 5 | 15 мар 2009 07:07 | 4 |
Leading zeroes Maxim Dvoynishnikov (Dnipropetrovsk NU) 14 мар 2009 13:20 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. |
| a problem | ddong | 1698. Квадратная страна 5 | 14 мар 2009 17:55 | 2 |
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. |
