5773. 【NOIP2008模拟】简单数学题

Description

话说，小X是个数学大佬，他喜欢做数学题。

有一天，小X想考一考小Y。他问了小Y一道数学题。题目如下：对于一个正整数N，存在一个正整数T（0<T<N），

使得的值是正整数。

小X给出N，让小Y给出所有可能的T。如果小Y不回答这个神奇的大佬的简单数学题,他学神的形象就会支离破碎。所以小Y求你帮他回答小X的问题。

Input

一个整数N。

Output

第一个数M，表示对于正整数N，存在M个不同的正整数T，

使得是整数。

后面是M个数，每一个数代表可能的正整数T（按从小到大的顺序排列）。

Solutions

设这个式子=K，得T=(2K-2)/(2K-1)*N,

然后只需枚举N的因数，判断2K-1等于因数时，是否为整数。

是，算出T，统计答案即可。

代码

 1 var
 2   n,m:int64;
 3   a:array [0..100001] of int64;
 4 procedure qsort(l,r:longint);
 5 var
 6   i,j:longint;
 7   mid,t:int64;
 8 begin
 9   if l>r then exit;
10   i:=l; j:=r;
11   mid:=a[(l+r) div 2];
12   repeat
13     while a[i]<mid do inc(i);
14     while a[j]>mid do dec(j);
15     if i<=j then
16       begin
17         t:=a[i]; a[i]:=a[j]; a[j]:=t;
18         inc(i); dec(j);
19       end;
20   until i>j;
21   qsort(i,r);
22   qsort(l,j);
23 end;
24 
25 procedure main;
26 var
27   i:longint;
28   k,t:int64;
29 begin
30   m:=0;
31   for i:=1 to trunc(sqrt(n)) do
32     if n mod i=0 then
33       begin
34         if (i+1) mod 2=0 then
35           begin
36             k:=(i+1) div 2;
37             t:=(k+k-2)*(n div i);
38             if (t>0) and (t<n) then
39               begin
40                 inc(m);
41                 a[m]:=t;
42               end;
43           end;
44         if (n div i+1) mod 2=0 then
45           begin
46             k:=(n div i+1) div 2;
47             t:=(k+k-2)*i;
48             if (t>0) and (t<n) then
49               begin
50                 inc(m);
51                 a[m]:=t;
52               end;
53           end;
54       end;
55 end;
56 
57 procedure print;
58 var
59   i,t:longint;
60 begin
61   t:=0;
62   for i:=1 to m-1 do
63     if a[i]=a[i+1] then
64       inc(t);
65   write(m-t);
66   for i:=1 to m do
67     if a[i]<>a[i+1] then
68       write(' ',a[i]);
69 end;
70 
71 begin
72   assign(input,'math.in');
73   assign(output,'math.out');
74   reset(input);
75   rewrite(output);
76   readln(n);
77   main;
78   qsort(1,m);
79   print;
80   close(input);
81   close(output);
82 end.