欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数论 HDU4990 快速幂模板

程序员文章站 2022-07-12 09:49:59
...

Reading comprehension

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3106    Accepted Submission(s): 1218

 

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

 

快速幂

if i为偶数       2^i = 2^(i/2) * 2^(i/2)     //快速呢!

else       2^i = 2^(i-1) * 2

板子:

//快速幂
long long pow(long long a,long long n,long long mod)
{
    long long ans=1;
    while(n){
        if(n&1){
            ans=(ans*a)%mod;
        }
        a=a*a%mod;
        n>>=1;  //>>=!!!!!
    }
    return ans%mod;
}

 

本题可以通过分析代码和前几位结果得出 ans(n) = 2^(n-1) + 2^(n-3) + ……  =  (4^((n+1)/2) -1) / 3 * (1或2)

注快速幂时的mod应是m的3倍。

 

#include <cstdio>

const int maxn=1e9;

long long n,m;

//快速幂
long long pow(long long n,long long mod)
{
    long long ans=1,a=4;
    while(n){
        if(n&1){
            ans=(ans*a)%mod;
        }
        a=a*a%mod;
        n>>=1;  //>>=!!!!!
    }
    return ans%mod;
}

int main()
{
    while(~scanf("%d%d",&n,&m)){
        long long ans=(pow((n+1)/2,m*3)-1)/3;       //注:除以3放在后面快速幂中的mod也要相应*3
        ans*=(n&1?1:2);
        printf("%lld\n",ans%m);
    }

    return 0;
}