10820  Send a Table
Moderator: Board moderators

 Experienced poster
 Posts: 149
 Joined: Mon Feb 07, 2005 10:28 pm
 Location: Northern University, Bangladesh
 Contact:
10820 Send a Table
Critical I/O please.

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: 10820 Send a Table
An input:
My AC's output:
Code: Select all
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
49950
49951
49952
49953
49954
49955
49956
49957
49958
49959
49960
49961
49962
49963
49964
49965
49966
49967
49968
49969
49970
49971
49972
49973
49974
49975
49976
49977
49978
49979
49980
49981
49982
49983
49984
49985
49986
49987
49988
49989
49990
49991
49992
49993
49994
49995
49996
49997
49998
49999
50000
0
Code: Select all
1
3
7
11
19
23
35
43
55
63
83
91
115
127
143
159
191
203
239
255
279
299
343
359
399
423
459
483
539
555
615
647
687
719
767
791
863
899
947
979
1059
1083
1167
1207
1255
1299
1391
1423
1507
1547
1611
1659
1763
1799
1879
1927
1999
2055
2171
2203
2323
2383
2455
2519
2615
2655
2787
2851
2939
2987
3127
3175
3319
3391
3471
3543
3663
3711
3867
3931
4039
4119
4283
4331
4459
4543
4655
4735
4911
4959
5103
5191
5311
5403
5547
5611
5803
5887
6007
6087
1516799635
1516885315
1516927939
1516994539
1517044491
1517122827
1517154507
1517254419
1517304375
1517356215
1517396151
1517493855
1517524095
1517618111
1517668071
1517721351
1517762679
1517859111
1517892327
1517991119
1518028847
1518095471
1518140111
1518216671
1518249983
1518329903
1518379871
1518446399
1518496375
1518587895
1518609399
1518708399
1518757503
1518824143
1518868943
1518942671
1518975983
1519058927
1519108911
1519171983
1519211967
1519311947
1519345259
1519445243
1519488083
1519536083
1519584243
1519677811
1519708531
1519808527
1519848527
I need to know how to deal with this ...
I 've tried to solve this problem, but i am never passing time limit.
I tried something like this :
i. for 1 ... Jimmy had to precalculate 1 value namely (1, 1)
ii. for i = 2 .. N, number of precalculated value = precalculated value for (i1) + (2*(no. of j(= 1..i1) that are relatively prime to i))
I use prime factoring to find those j's.
Is there anything wrong with my algo.? or, else how can i make it faster(it is not passing the limit )?
I tried something like this :
i. for 1 ... Jimmy had to precalculate 1 value namely (1, 1)
ii. for i = 2 .. N, number of precalculated value = precalculated value for (i1) + (2*(no. of j(= 1..i1) that are relatively prime to i))
I use prime factoring to find those j's.
Is there anything wrong with my algo.? or, else how can i make it faster(it is not passing the limit )?
Dear Ryan pai,
Thanks a lot, I just got ACC , now it takes 0.096sec(Now, i 've passed the limit...).
I use Euler's phi function just as you 've mentioned, my factoring was a bit okay, but to factor out the multiples of factors, I used something like sieve ... and for marking and unmarking, I use loops and memset() everytime ... I guess that was the bottleneck. Anyway, thanks a lot ...
Thanks a lot, I just got ACC , now it takes 0.096sec(Now, i 've passed the limit...).
I use Euler's phi function just as you 've mentioned, my factoring was a bit okay, but to factor out the multiples of factors, I used something like sieve ... and for marking and unmarking, I use loops and memset() everytime ... I guess that was the bottleneck. Anyway, thanks a lot ...
I also have time problem
I use totient function , but it still needs factoring,
I use this : if (m,n)=1， f(mn)=f(m)f(n)
but I find it cost time when I divide a numer m*n into m,n
can someone help me
I use this : if (m,n)=1， f(mn)=f(m)f(n)
but I find it cost time when I divide a numer m*n into m,n
can someone help me
Hint
To xlvector:
I think it's enough to evaluate f(n):
int f(int n)
{
int result = n;
for(int i=2;i*i <= n;i++)
{
if (n % i == 0) result = result / i;
while (n % i == 0) n /= i;
}
if (n > 1) result = result / n;
return result;
}
Then precompute all f(n), n=1,50000. And will get ACC.
Still wa  write me, I got acc.
I think it's enough to evaluate f(n):
int f(int n)
{
int result = n;
for(int i=2;i*i <= n;i++)
{
if (n % i == 0) result = result / i;
while (n % i == 0) n /= i;
}
if (n > 1) result = result / n;
return result;
}
Then precompute all f(n), n=1,50000. And will get ACC.
Still wa  write me, I got acc.
Hi,
If I remember correctly, I also used something like sieve...
I'm currently ranked #2 for this task. But I have no idea how 0.00.002 can be achieved.... Faster I/O?
If I remember correctly, I also used something like sieve...
I'm currently ranked #2 for this task. But I have no idea how 0.00.002 can be achieved.... Faster I/O?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
Good for you~ Don't want to improve my code, since I think it is now short (14 lines) and beautiful. (And the other reason is of course I don't know what I can improve )Krzysztof Duleba wrote:Now you're third
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
okay, maybe not that impressive... One of the lines read:
which is long, though I find no reason to break it into several lines.
Code: Select all
for (i=3;i<=223;i+=2) if (!fac[i]) for (s=i*i;s<=50000;s+=i<<1) fac[s]=i;
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org