首页 > ACM题库 > HDU-杭电 > HDU 2837-Calculation[解题报告]HOJ
2014
02-17

HDU 2837-Calculation[解题报告]HOJ

Calculation

问题描述 :

Assume that f(0) = 1 and 0^0=1. f(n) = (n%10)^f(n/10) for all n bigger than zero. Please calculate f(n)%m. (2 ≤ n , m ≤ 10^9, x^y means the y th power of x).

输入:

The first line contains a single positive integer T. which is the number of test cases. T lines follows.Each case consists of one line containing two positive integers n and m.

输出:

The first line contains a single positive integer T. which is the number of test cases. T lines follows.Each case consists of one line containing two positive integers n and m.

样例输入:

2
24 20
25 20

样例输出:

16
5

#include<stdio.h>
#include<math.h>
#include<string.h>
#define LL long long
const int M=100000+10;
int vis[M],pri[M];
LL oula(LL s)
{
 LL ss=s,tmp=sqrt(s+0.5);
 for(int i=0;pri[i]<=tmp;i++)
 if(s%pri[i]==0)
 {
 ss=ss/pri[i]*(pri[i]-1);
 while(s%pri[i]==0)
 s/=pri[i];
 if(s==1)break;
 }
 if(s>1)ss=ss/s*(s-1);
 return ss;
}
LL powmod(LL a,LL p,LL mod)
{
 LL ans=1;
 while(p)
 {
 if(p&1)
 {
 ans=ans*a;
 if(ans>mod)
 ans=ans%mod+mod;
 }
 a=a*a;
 if(a>mod)
 a=a%mod+mod;
 p>>=1;
 }
 return ans;
}
LL solve(LL n,LL m)
{
 if(n<10)return n;
 LL mm=oula(m);
 LL poi=solve(n/10,mm);
 return powmod(n%10,poi,m);
}
int main()
{
 int i,j,k=0,t;
 LL n,m;
 for(i=2;i*i<M;i++)if(!vis[i])
 for(j=i*i;j<M;j+=i)
 vis[j]=1;
 for(i=2;i<M;i++)if(!vis[i])
 pri[k++]=i;
 scanf("%d",&t);
 while(t--)
 {
 scanf("%I64d%I64d",&n,&m);
 printf("%I64d\n",solve(n,m)%m);
 }
 return 0;
}

  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.