竹園論壇

標題: a568 - ISSC 2012- problem B [打印本頁]

作者: Sylveon 時間: 2014-6-26 17:21
標題: a568 - ISSC 2012- problem B
原題：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);
}
}

歡迎光臨竹園論壇 (http://forum.tfcis.org/)