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 Fibonaccinumbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).

Input

Input consists of a sequenceof 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;elsecout<<"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 positiveinteger N, you should output the most right digit of N^N.

Input

The input containsseveral test cases. The first line of the input is a single integer T which isthe 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 testcase, 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.  N！Again

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:                                     Iwant to calculate N!......
WhereIsHeroFrom:            Soeasy! How big N is ?
Zty:                                    1<=N <=1000000000000000000000000000000000000000000000…
WhereIsHeroFrom:            Oh! Youmust 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 willcontain 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

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

原文地址：https://www.cnblogs.com/czc1999/p/10111573.html