Reading comprehension
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1270 Accepted Submission(s): 512
Problem DescriptionRead the program below carefully then answer the question.
#pragma comment(linker, “/STACK:1024000000,1024000000”)
#include <cstdio>
#include<iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include<vector>
const int MAX=100000*2;
const int INF=1e9;
int main()
{
int n,m,ans,i;
while(scanf(“%d%d”,&n,&m)!=EOF)
{
ans=0;
for(i=1;i<=n;i++)
{
if(i&1)ans=(ans*2+1)%m;
else ans=ans*2%m;
}
printf(“%d\n”,ans);
}
return 0;
} InputMulti test cases,each line will contain two integers n and m. Process to end of file.
[Technical Specification]
1<=n, m <= 1000000000 OutputFor each case,output an integer,represents the output of above program. Sample Input1 10
3 100 Sample Output1
5 Source BestCoder Round #8 这个题就是需要用log(n)解决上面的程序问题。然后我们找奇数项的关系。f[2k+1] = 2*f[2k] + 1 (k>=1)f[2k] = 2*f[2k-1]代入可得 f[2k+1] = 4*f[2k-1]+1 => bi = 4*bi-1+1bi = 4*bi-1+1bi-1 = 4*bi-2+1..b3 = 4*b2 + 1b2 = 4*b1 +1 可得bk = 1+4+4^2+….+4^k-1k与n之间的映射是 k = (n+1)/2 然后带入模板算就OK。偶数的话乘2.
#include <cstdio>
#include<iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include<vector>
typedef long long LL;LL mod;
LL pow_mod(LL a,LL n){
LL ans = ;
while(n){
if(n&) ans=ans*a%mod;
a= a*a%mod;
n>>=;
}
return ans;
}
LL cal(LL p,LL n){ ///这里是递归求解等比数列模板 1+p+p^2...+p^n
if(n==) return ;
if(n&){///(1+p+p^2+....+p^(n/2))*(1+p^(n/2+1));
return (+pow_mod(p,n/+))*cal(p,n/)%mod;
}
else { ///(1+p+p^2+....+p^(n/2-1))*(1+p^(n/2+1))+p^(n/2);
return (pow_mod(p,n/)+(+pow_mod(p,n/+))*cal(p,n/-))%mod;
}
}int main()
{
LL n;
while(scanf("%lld%lld",&n,&mod)!=EOF)
{
if(n==&&mod==) {
printf("0\n");
continue;
}
LL k = (n+)/;
LL ans = cal(,k-);
if(n&){
printf("%lld\n",ans);
}else {
printf("%lld\n",ans*%mod);
}
}
return ;
}