BZOJ3288 Mato矩阵 - Hoblovski's Blog - 想拿Ag的蒟蒻.已经Ag滚出.
BZOJ1927 Starrace
BZOJ3289 Mato文件管理

BZOJ3288 Mato矩阵

Hoblovski posted @ 2014年7月12日 20:58 in Solutions with tags 矩阵 高斯消元 bzoj 行列式 找规律 欧拉筛 , 882 阅读
题意
N×N方阵A,a(i,j)=gcd(i,j),求det(A)
N!>1000000
 
Tag 行列式,高斯消元,找规律,欧拉筛
 
这道题的分数-时间曲线十分畸形,除非你不会行列式和线性筛,否则就是想通100分否则0分(我们暂且认为高斯消元求行列式0分)
如果你打出前几个数不能发现什么规律,除了答案合成度非常高,要看出来就真是神牛了Orzzzz.
但是我们考虑基础行列式的变换,从第一行开始每行向下消元消成上三角矩阵.
我们发现a(i,i)=phi(i)之后得到答案Ans=Pi(phi(i)),欧拉-JZP大法好.
Mato三题还剩最后一题
 
program bzoj3288;
 
const maxn=1000017;
      mo=1000000007;
 
var p:array[0..maxn] of boolean;
    prime,phi:array[0..maxn] of longint;
    n,cp:longint;
 
procedure sieve(n:longint);
var i,j:longint;
begin
fillchar(p,sizeof(p),true); p[1]:=false; cp:=0; phi[1]:=1;
for i:=1 to n do begin
        if p[i] then begin
                inc(cp); prime[cp]:=i;
                phi[i]:=i-1;
        end; for j:=1 to cp do if i*prime[j]<=n then begin
                p[i*prime[j]]:=false; if i mod prime[j]=0 then begin
                        phi[i*prime[j]]:=phi[i]*prime[j]; break;
                end else phi[i*prime[j]]:=phi[i]*phi[prime[j]];
        end else break;
end;
end;
 
function piphi(n:longint):longint;
var i:longint;
begin
piphi:=1; for i:=1 to n do piphi:=int64(piphi)*phi[i]mod mo;
end;
 
begin
readln(n);
sieve(n);
writeln(piphi(n));
end.

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter