2014
02-17

# 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.