poj 3406 (勒让德定理)

Bertha 。 2022-06-10 07:40 215阅读 0赞

Last digit

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 3168</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 966</td> 
  </tr> 
 </tbody> 
</table>

Description

Determine the last nonzero digit in value of expression

![formula_tex_C_n_5Em_3D_5Cfrac_7Bn_21_7D_7Bm_21_28n-m_29_21_7D][].

Input

The input contains a single line with *n* and *m* separated by one or several spaces; *n*, *m* are natural numbers from 1 to 1000000, *n* ≥ *m*.

Output

The output contains a single line with the last nonzero digit.

Sample Input

4 2

Sample Output

题目题意:让你求该组合数的非0的末尾的数字.

题目分析:因为我们看到n和m的数值非常大，所以我们不可能直接利用公式求解。我们要想办法把这个分式化简。我们注意到任何数大于2的正整数到可以分解成素数的乘积，如果我们能把分数的分子和分母的公共质因子都划出，就减小很大了。

勒让德定律可以帮我们快速求出n!的质因子。

在正数n!的素因子标准分解式中，素数p的指数记作

![0b55b319ebc4b7457537478fcdfc1e178b821583.jpg][]

，则

![d009b3de9c82d1582c86aa28820a19d8bc3e4227.jpg][]

接下来就是解决非0问题，很简单，应该只有5\*2=10，末尾有0，所以我们成对的消除就行了。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    const int maxn=1e6+10;
    int prime[maxn],cnt;
    bool vis[maxn];
    int ans[maxn][3];
    void get_prime()//质数打表
    {
        memset (vis,true,sizeof (vis));
        vis[1]=false;
        for (int i=2;i<maxn;i++) {
            if (vis[i]) prime[cnt++]=i;
            for (int j=0;j<cnt&&i*prime[j]<maxn;j++) {
                vis[i*prime[j]]=false;
                if (i%prime[j]==0) break;
            }
        }
    }
    int get_sum(int p,int n)//勒让德定律，求出n!标准分解式中，素数P的指数
    {
        int ans=0;
        while (n) {
            ans+=n/p;
            n=n/p;
        }
        return ans;
    }
    
    int fast_pow(int base,int k)//快速幂
    {
        int ans=1;
        while (k) {
            if (k&1)
                ans=ans*base;
            base=base*base;
            k>>=1;
        }
        return ans;
    }
    int main()
    {
        get_prime();
        int n,m;
        while (scanf("%d%d",&n,&m)!=EOF) {
            memset (ans,0,sizeof (ans));
            for (int i=0;i<cnt&&prime[i]<=n;i++)//将n!分解
                ans[i][0]=get_sum(prime[i],n);
            for (int i=0;i<cnt&&prime[i]<=m;i++)//将m!分解
                ans[i][1]=get_sum(prime[i],m);
            for (int i=0;i<cnt&&prime[i]<=n-m;i++)//将(n-m)!分解
                ans[i][2]=get_sum(prime[i],n-m);
            for (int i=0;i<cnt&&prime[i]<=n;i++)//约掉公共质因子的指数
                ans[i][0]-=(ans[i][1]+ans[i][2]);
            if (ans[0][0]>ans[2][0]) {//处理非0，当2的指数大于5的指数时
                ans[0][0]-=ans[2][0];
                ans[2][0]=0;
            }
            else {//否则
                ans[2][0]-=ans[0][0];
                ans[0][0]=0;
            }
            int res=1;
            for (int i=0;i<cnt&&prime[i]<=n;i++) {//挨个求，mod/10
                if (ans[i][0]==0) continue;
                res=res*fast_pow(prime[i],ans[i][0]);
                res=res%10;
            }
            cout<<res<<endl;
        }
        return 0;
    }

[formula_tex_C_n_5Em_3D_5Cfrac_7Bn_21_7D_7Bm_21_28n-m_29_21_7D]: /images/20220610/f42ebb0c1aef4fb794b0615eb7184b60.png
[0b55b319ebc4b7457537478fcdfc1e178b821583.jpg]: https://gss2.bdstatic.com/-fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D44/sign=02369b768fb1cb133a693d17dc540b7a/0b55b319ebc4b7457537478fcdfc1e178b821583.jpg
[d009b3de9c82d1582c86aa28820a19d8bc3e4227.jpg]: https://gss0.bdstatic.com/94o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D122/sign=cee465657ed98d1072d40833133eb807/d009b3de9c82d1582c86aa28820a19d8bc3e4227.jpg