a568 - ISSC 2012- problem B

Sylveon

原題：http://zerojudge.tw/ShowProblem?problemid=a568
AC：http://zerojudge.tw/Submissions?problemid=a568&account=lfs92002
解題方法：數學解

考慮兩個N位數[tex]A,B[/tex]，則可把要求的數字P表示成[tex]A%20%5Ctimes%2010%5E%7BN+1%7D+B[/tex]，求取使P整除A,B的所有P之個數。

[tex]Follow%20Steps%3A%5C%5C%20G%3DA%5Ctimes%2010%5EN+B%5C%5C%20%5C%5C%20G%5C%25%20A%3D0%5Crightarrow%20B%5C%25A%3D0%5Crightarrow%20B%3DkA%281%5Cleq%20k%3C10%29%5C%5C%20%5C%5C%20G%5C%25%20B%3D0%5Crightarrow%20A%5Ctimes%2010%5EN%5C%25B%3D0%5C%5C%20%5Crightarrow%20A%5Ctimes%2010%5EN%5C%25%28kA%29%3D10%5EN%5C%25k%3D0%5C%5C%20%5C%5C%20%5Ctherefore%20k%3D1%2C2%2C5%2C4%28N%5Cgeq%202%29%2C8%28N%5Cgeq%203%29[/tex]

可得B必為A的1,2,4,5,8倍，那只要把[tex]10^N/k-10^{N-1}[/tex]都加起來即可，看起來很麻煩的模運算除法可以由提出10的次方先約掉，變成乘法運算後再取模，即可輕鬆求解。


/**********************************************************************************/
/*  Problem: a568 "ISSC 2012- problem B" from ISSC 2012                           */
/*  Language: CPP (549 Bytes)                                                     */
/*  Result: AC(1.8s, 256KB) judge by this@ZeroJudge                               */
/*  Author: lfs92002 at 2014-06-26 17:18:54                                       */
/**********************************************************************************/


#include<cstdio>
using namespace std;

int mpow(int a,int e,int m)
{
    if(e==0)return 1;
    int p=mpow(a*a%m,e/2,m);
    if(e%2==0)return p;
    return p*a%m;
}

int main()
{
    const int ansOfNe1=14;
    int N,M;
    while(~scanf("%d%d",&N,&M))
    {
        int En=mpow(10,N-1,M);
        int sum=0;
        //K=1
        sum=(10*En-En)%M;
        //K=2
        sum+=(5*En-En)%M;
        //K=5
        sum+=(2*En-En)%M;
        //K=4 for N>=2
        if(N>=2)
        sum+=(25*mpow(10,N-2,M)-En+25*M)%M;
        //K=8 for N>=3
        if(N>=3)
        sum+=(125*mpow(10,N-3,M)-En+125*M)%M;
        printf("%d\n",sum%M);
    }
}