HDU 4704 Sum （2013多校10,1009题）

Sum

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 94    Accepted Submission(s): 41

Problem Description

Sample Input

2

Sample Output

2

Hint

1. For N = 2, S(1) = S(2) = 1.

2. The input file consists of multiple test cases.

Source

2013 Multi-University Training Contest 10

Recommend

zhuyuanchen520

其实这题就是求2^(n-1) % MOD;

可先对(n-1)%(MOD-1)

这样就很容易求了

 /* ***********************************************
 Author        :kuangbin
 Created Time  :2013/8/22 12:00:50
 File Name     :F:\2013ACM练习\2013多校10\1009.cpp
 ************************************************ */

 #include <stdio.h>
 #include <string.h>
 #include <iostream>
 #include <algorithm>
 #include <vector>
 #include <queue>
 #include <set>
 #include <map>
 #include <string>
 #include <math.h>
 #include <stdlib.h>
 #include <time.h>
 using namespace std;

 const int MOD = 1e9+;
 long long n;
 long long solve()
 {
     long long ret = ;
     long long tmp = ;
     while( n > )
     {
         if(n%)
         {
             ret *= tmp;
             ret %= MOD;
         }
         tmp *= tmp;
         tmp %= MOD;
         n = n/;
     }
     return ret;
 }
 char str[];
 int main()
 {
     //freopen("in.txt","r",stdin);
     //freopen("out.txt","w",stdout);
     while(scanf("%s",str) == )
     {
         n = ;
         int len = strlen(str);
         for(int i = ;i < len;i++)
         {
             n = (n* + str[i] -'')%(MOD-);
         }
         n = (n-+MOD-)%(MOD-);
         printf("%d\n",(int)solve());
     }
     return ;
 }