「考试」num （破800纪念）

是第800题啦。

怎么说，$rvalue$学长写的已经挺好的了，我在这里做一点补充，写一点理解。

但是这道题真的值得写一下题解，毕竟一百行也算是数论工程题了。

定义函数

$Fp(k,n)$为$n$中$k$的最大幂次。

$Ext(k,n)=n/Fp(k,n)$

我们要求的就是$Ext(10,n!)%1000$

怎么做。

首先$Ext$函数在$k$为质数的情况下是完全积性函数。（这里zsq学长出锅了，没有说k是质数）

这个证都不用证吧。。。根据定义直接出了。

好到这步我都懂，甚至看到最后我都懂。

可是根本想不到。

这一步就是切入题目的最关键点了。

为什么要设立这样一个函数。

其实目的就是转化问题，本来让人摸不着头脑的题一下子思路就清晰起来了。

可能这就是公式思想。把不会的转化为公式，然后用数学方法死刚公式就行了。

然而$10$不是质数，不是很好求，所以我们用$CRT$合并对$Ext(10,n!)$求解。

代出两个互质部分的式子。

$Ext(10,n!)=\frac{n!}{2^{Fp(5,n!)}5^{Fp(5,n!)}}$

一种经典的$O(log_5(n))$阶乘求因子方法，可以很快的求出$Fp(5,n!)$，$2^c$和$5^c$互质，可以直接欧拉定理求逆元。

所以其实求$Ext(5,n!)$即可。

在$K==1$的时候。我们将$10$拆分成$2$和$5$。

利用$Ext$的完全积性。

$Ext(5,n!) \equiv \prod \limits_{i=1}^{n!}Ext(5,i)(mod\ 5)$

$\equiv \prod \limits_{i=1,5|i}^{n!}Ext(5,\frac{i}{5})\prod \limits_{i=1,5\perp i}^{n}Ext(5,i)(mod\ 5)$

$\equiv Ext(5,\frac{n!}{5})\prod \limits_{i=1,5\perp i}^{n}i(mod\ 5)$

$\equiv Ext(5,\frac{n!}{5})(\prod \limits_{i=1,5\perp i}^{5}i)^{\frac{n}{5}} \prod \limits_{i=1,5\perp i}^{n\%5} i (mod\ 5)$

发现是个递归式。

一千的话，同理也可以快速递归的到答案。

但是要写高精所以就很麻烦了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int maxn=1e2+;

 typedef long long ll;

 inline void read(int &x)

 {

     x=;char c=getchar();

     while(c<''||c>'') c=getchar();

     while(c>=''&&c<='') x=(x<<)+(x<<)+c-,c=getchar();

 }

 const int tw[]={,,,},fi[]={,,,},phif[]={,,,},mo[]={,,,};

 int T,K,tc,fr,se,num;

 char s[maxn];

 int add(int x,int y,int mod) {return x+y>=mod?x+y-mod:x+y;}

 int mul(int x,int y,int mod) {return 1LL*x*y%mod;}

 int qw(int a,int b,int mod)

 {

     int ans=;

     for(;b;b>>=,a=mul(a,a,mod)) if(b&) ans=mul(ans,a,mod);

     return ans;

 }

 struct Bigdata{

     int a[maxn];

     bool isz() {return a[]==&&a[a[]]==;}

     void init(char *s)

     {

         memset(a,,sizeof(a));

         a[]=strlen(s+);

         for(int i=a[];i>=;--i) a[i]=s[a[]-i+]-;

     }

     void divf(int m)

     {

         int x=;

         for(int i=a[];i>=;--i) x=x*+a[i],a[i]=x/m,x%=m;

         while(!a[a[]]&&a[]>) --a[];

     }

     int getm(int mod)

     {

         int res=;

         for(int i=a[];i>=;--i) res=add(a[i],mul(res,,mod),mod);

         return res;

     }

     int getn() {int res=;for(int i=a[];i>=;--i) res=res*+a[i];return res;}

     void print() {for(int i=;i<=a[];++i) printf("%d",a[i]);puts("");}

 }n,tmp;

 int nfac(Bigdata &t,int m,int mod)

 {

     int ans=;

     while(!t.isz())

     {

         t.divf(m);

         ans=add(ans,t.getm(mod),mod);

     }

     return ans;

 }

 void lit(int n,int K)

 {

     const int mod=1e5;ll ans=;

     for(int j=,t=j;j<=n;++j,t=j)

     {

         while(!(t%)) t/=;t%=mod;ans*=t;

         while(!(ans%)) ans/=;ans%=mod;

     }

     for(int i=K;i>=;--i) printf("%lld",(ans/mo[i-])%);puts("");

 }

 int Ext()

 {

     if(n.isz()) return ;

     int up=n.getm(fi[K]);

     tmp=n;tmp.divf(fi[K]);n.divf();

     int tc=tmp.getm(phif[K]),t=;

     for(int i=;i<=up;++i) if(i%) t=mul(t,i,fi[K]);

     return mul(mul(qw(num,tc,fi[K]),t,fi[K]),Ext(),fi[K]);

 }

 int main()

 {

 //    freopen("ex_num2.in","r",stdin);

 //    freopen("a.out","w",stdout);

     read(T);

     while(T--)

     {

         scanf("%s",s+);n.init(s);read(K);

         if(n.a[]<=) {lit(n.getn(),K);continue;}

         tmp=n;

         tc=nfac(tmp,,phif[K]);

         fr=qw(qw(,tc,fi[K]),phif[K]-,fi[K]);

         for(int i=num=;i<=fi[K];++i) if(i%) num=mul(num,i,fi[K]);

         se=Ext();

         se=mul(se,fr,fi[K]);

         while(se%tw[K]) se=add(se,fi[K],tw[K]*fi[K]);

         for(int i=K;i>=;--i) printf("%d",(se/mo[i-])%);puts("");

     }

     return ;

 }

num

最后$%%%zsq$学长，教我多项式，题解写的又好。

巴特西

「考试」num （破800纪念）

最新文章

热门文章