快速幂 HDU-1021 Fibonacci Again , HDU-1061 Rightmost Digit , HDU-2674 N!Again

1.   Fibonacci Again

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 77116    Accepted Submission(s): 34896

Problem Description

There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).

  

Input

Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000).

 

Output

Print the word "yes" if 3 divide evenly into F(n).

Print the word "no" if not.

 

Sample Input

0
1
2
3
4
5

 

Sample Output

no
no
yes
no
no
no

数据级别在1,000,000,就正常做不会超时,最简单的快速幂,根据 (a * b) % p = (a % p * b % p) % p 。
#include <iostream>#include <stdio.h>using namespace std;int main(){ int n; while(scanf("%d",&n)!=EOF){ int f0=7,f1=11; int fn; for(int i=2;i<=n;i++){ fn=(f0+f1)%3; f0=f1%3; f1=fn%3; } if(n<=1){ cout<<"no"<<endl; } else{ if(fn%3==0) cout<<"yes"<<endl; else cout<<"no"<<endl; } } return 0;}

  

2.  Rightmost Digit

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 71510    Accepted Submission(s): 26554

 

Problem Description

Given a positive integer N, you should output the most right digit of N^N.

 

Input

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case contains a single positive integer N(1<=N<=1,000,000,000).

 

Output

For each test case, you should output the rightmost digit of N^N.

 

Sample Input

2

3

4

 

Sample Output

7

6


 

 数据级别10亿,上一种就无法完成了,需要用另一种方法降低n的规模。

#include <iostream>#include <stdio.h>using namespace std;int main(){ int k; cin>>k; while(k--){ long long n; cin>>n; long long res=1;long long a=n,b=n; while(b){ if(b&1) res=(res*a)%10; a=(a*a)%10; b/=2; } cout<<res<<endl; } return 0;}

 

3.  NAgain

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

Problem Description

WhereIsHeroFrom:             Zty, what are you doing ?
Zty:                                     I want to calculate N!......
WhereIsHeroFrom:             So easy! How big N is ?
Zty:                                    1 <=N <=1000000000000000000000000000000000000000000000…
WhereIsHeroFrom:             Oh! You must be crazy! Are you Fa Shao?
Zty:                                     No. I haven‘s finished my saying. I just said I want to calculate N! mod 2009

Hint : 0! = 1, N! = N*(N-1)!

Input

Each line will contain one integer N(0 <= N<=10^9). Process to end of file.

 

Output

For each case, output N! mod 2009

 

Sample Input

4

5

 

Sample Output

24

120


 

 10^9这种数据级别已经不是正常做法能解出来的了,一定有特殊数据,试一下就能找到。

#include <iostream>#include <stdio.h>using namespace std;int main() { long long n; while(scanf("%lld",&n)!=EOF){ long long res=1; if(n>=41) cout<<0<<endl; else{   for(int i=1;i<=n;i++){ res=(res*i)%2009; } cout<<res<<endl; } } return 0;}

 各种快速幂很详细:https://yq.aliyun.com/wenji/254837

相关文章