HDU 4990 Reading comprehension

Problem Description

Read 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;

}

Input

Multi test cases，each line will contain two integers n and m. Process to end of file.

[Technical Specification]

1<=n, m <= 1000000000

Output

For each case，output an integer，represents the output of above program.

Sample Input

1 10

3 100

Sample Output

1

5

#include <stdio.h>
#define ll long long
void slove(int n,ll mod,ll ret){
    ll T=4;
    while(n){
        if(n&1) ret=(ret*T)%mod;
        T=(T*T)%mod;
        n/=2;
    }
    printf("%d\n",ret/3);
}
int main(){
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF){
        slove((n+1)/2,(ll)(m)*3,2-(n&1));
    }
    return 0;
}