题目链接

https://vjudge.net/problem/HDU-4990

题面

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

题意

阅读程序，写出答案

题解

我现在觉得偶数的规律比较好找，就以找偶数的规律为例吧。

第一个偶数二进制是10，第二个是1010，第三个是101010...这样可以很容易算出偶数的时候即为\(2\times(4^0+4^1+...+4^{\frac{n-2}{2}})\)等比公式求和即为\(\frac{2^{n+1}-2}{3}\)，对于偶数，我们快速幂算出这个结果即可，但是有除法之后取模，所以我们要处理一下，可以直接对3*m取模。即
\[ ans=\frac{a}{b}\%m \Leftrightarrow ans= \frac{a\%(bm)}{b} \]
推导如下
\[ \frac{a}{b}\%m=x\\frac{a}{b}=km+x\a=kbm+bx\a\%(bm)=bx\\frac{a\%(bm)}{b}=x=\frac{a}{b}\%m \]

也可以这么理解，%3m的话结果就会在3m中，再除以3结果必定在m中，就达到了对m取模相同的效果

但要注意一点然后根据偶数推出奇数就可以了。

当初代码是先推得奇数再推出偶数

AC代码

#include <bits/stdc++.h>
using namespace std;
long long n, m;
long long fast_pow(long long a, long long b) {
    long long ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}
int main() {
    while (scanf("%lld%lld", &n, &m) != EOF) {
        long long last = m;
        m = m * 3;
        long long ans = 0;
        if (n & 1) {
            ans = (fast_pow(2, n + 1) - 1) % m / 3;
        }
        else {
            ans = (fast_pow(2, n) - 1) % m / 3;
            ans = ans * 2 % last;
        }
        cout << ans << endl;
    }
    return 0;
}

HDU-4990 Reading comprehension

原文：https://www.cnblogs.com/artoriax/p/10376346.html