Noip 2014 Day 2 T 3解方程式

理論上70点
a[i]を大きな質量数でモード化し,次いでO(nm)
p=10^7+7比較科学

program ttt;
const p=10000007;
var n,v,j,m,t,i,ss:longint;
    a:array[0..100]of longint;
	c:array[1..100000]of longint;
procedure readdata(i:longint);
var s:int64;
    ch:char;
begin
 s:=0;
 read(ch);
 if ch='-' then 
  begin 
   a[i]:=-1;
   read(ch);
  end
 else
  a[i]:=1;
 while (ch>='0')and(ch<='9') do 
  begin 
   s:=(s*10+(ord(ch)-48)) mod p;
   read(ch);
  end;
 a[i]:=a[i]*s;
 readln;
end;
  
begin
 readln(n,m);
 for i:=0 to n do
  readdata(i);
 for i:=1 to m do
  begin
   v:=a[n];
   for j:=n-1 downto 0 do
    v:=(v*i+a[j]) mod p;//     
   if v=0 then 
    begin
	 ss:=ss+1;
	 c[ss]:=i;
	end;
  end;
 writeln(ss);
 for i:=1 to ss do
  writeln(c[i]);
 readln;readln;
end.

ふるいほう
100点:
f(x+p)=f(x)+T
p|T
∴f(x+p)≡f(x) (mod p)
周期性がある
だからいくつかの小さい質量数を選んでxを検査することができます
同様にint 64の使用に注意

program ttt;
const p:array[1..10]of longint=(1007,10007,12347,12349,100017,111647,19720308,19750920,19981117,20150208);
var n,kk,j,m,i,ss:longint;
	t,v:int64;
    a:array[0..100,1..10]of int64;
	inner:array[1..1000000]of boolean;
	c:array[1..1000000]of longint;
procedure readdata(i:longint);
var s:array[1..10]of int64;
    ch:char;
begin
 fillchar(s,sizeof(s),0);
 read(ch);
 if ch='-' then 
  begin 
   for kk:=1 to 10 do a[i][kk]:=-1;
   read(ch);
  end
 else
  for kk:=1 to 10 do a[i][kk]:=1;
 while (ch>='0')and(ch<='9') do 
  begin 
   for kk:=1 to 10 do 
    s[kk]:=(s[kk]*10+(ord(ch)-48)) mod p[kk];
   read(ch);
  end;
 for kk:=1 to 10 do a[i][kk]:=a[i][kk]*s[kk];
 readln;
end;
 
function check2(i,kk:longint):boolean;
var t,j:longint;
	v:int64;
begin
 v:=a[n][kk];
 for j:=n-1 downto 0 do
  v:=(v*i+a[j][kk]) mod p[kk];
 if v<>0 then//         
  begin
   t:=i;
   while t<=m do
    begin
	 inner[t]:=false;
	 t:=t+p[kk];
	end;
   exit(false);
  end
 else
  exit(true);
end;

function check(i:longint):boolean;
var j:longint;
begin
 if inner[i]=false then exit(false);//  
 for j:=1 to 10 do//  10   
  if check2(i,j)=false then exit(false);
 exit(true);
end;
  
begin
 readln(n,m);
 for i:=0 to n do
  readdata(i); //a[i,kk]  ai mod p[kk]
 fillchar(inner,sizeof(inner),true);
 for i:=1 to m do //          
  begin
   if check(i) then 
    begin
	 ss:=ss+1;
	 c[ss]:=i;
	end;
  end;
 writeln(ss);
 for i:=1 to ss do
  writeln(c[i]);
 readln;readln;
end.