5809. 【NOIP2008模拟】数羊

2024-07-09 12:56| 来源: 网络整理| 查看: 265

Solution

对于100%的数据，我们将a进行质因数分解，将每个质因子的指数乘上b，

最后的答案就是等比数列的和，但是由于涉及取模，所以我们除法要用逆元。

在下比较菜，记一下逆元怎么用：

$(\frac{a}{b})\;\; mod \;\; p=(a*b^{(p-2)})\;\; mod\;\; p$

代码

1 const 2 mo=9901; 3 var 4 n,m,nm,ans:longint; 5 function mi(x,tk:int64):longint; 6 var 7 t:int64; 8 begin 9 t:=1; 10 while tk>0 do 11 begin 12 if tk mod 2=1 then 13 t:=(t*x) mod mo; 14 x:=(x*x) mod mo; 15 tk:=tk div 2; 16 end; 17 exit(t); 18 end; 19 20 procedure main; 21 var 22 i,t,j,tt,kk:longint; 23 begin 24 i:=2; t:=n; ans:=1; 25 while t1 do 26 begin 27 j:=0; 28 while t mod i=0 do 29 begin 30 inc(j); 31 t:=t div i; 32 end; 33 if j>0 then 34 begin 35 tt:=mi(i,j*m+1)-1; 36 kk:=mi(i-1,mo-2); 37 ans:=ans*(tt*kk) mod mo; 38 end; 39 inc(i); 40 end; 41 end; 42 43 begin 44 assign(input,'sheep.in'); 45 assign(output,'sheep.out'); 46 reset(input); 47 rewrite(output); 48 readln(n,m); 49 main; 50 writeln(ans); 51 close(input); 52 close(output); 53 end.

【本文地址】

公司简介

联系我们