首页 > ACM题库 > HDU-杭电 > Hdu 1852 Beijing 2008-数学[解题报告] C++
2013
12-23

Hdu 1852 Beijing 2008-数学[解题报告] C++

Beijing 2008

问题描述 :

As we all know, the next Olympic Games will be held in Beijing in 2008. So the year 2008 seems a little special somehow. You are looking forward to it, too, aren’t you? Unfortunately there still are months to go. Take it easy. Luckily you meet me. I have a problem for you to solve. Enjoy your time.

Now given a positive integer N, get the sum S of all positive integer divisors of 2008N. Oh no, the result may be much larger than you can think. But it is OK to determine the rest of the division of S by K. The result is kept as M.

Pay attention! M is not the answer we want. If you can get 2008M, that will be wonderful. If it is larger than K, leave it modulo K to the output. See the example for N = 1,K = 10000: The positive integer divisors of 20081 are 1、2、4、8、251、502、1004、2008,S = 3780, M = 3780, 2008M % K = 5776.

输入:

The input consists of several test cases. Each test case contains a line with two integers N and K (1 ≤ N ≤ 10000000, 500 ≤ K ≤ 10000). N = K = 0 ends the input file and should not be processed.

输出:

For each test case, in a separate line, please output the result.

样例输入:

1  10000
0  0

样例输出:

5776

// 这题主要求S
// 结论: S = (251^(n+1)-1) * (2^(3n+1)-1) / 250 
// 是两个等比数列和相乘 
// 
// 推理:
// 2008 = 2^3 * 251 
// 所以 2008^N 有 3N 个 2 和 N 个251 
// 所有仅由2组成的因子有
// 2^0 2^1 2^2 ... 2^(3N)
// 设集合 C = {2^0, 2^1, 2^2 ...,2^(3N)};
// SUM(C) =  2^(3n+1)-1

// 跟251组合产生的因子有
// 251^0 * C
// 251^1 * C
// ...
// 251^N * C

// 所有因子和为:
// S = (251^(n+1)-1))/250 * (2^(3n+1)-1)

// 计算S%K:
// S 很大, 不能保存在普通的数据类型中, 需要直接计算S%K
// 因为S有个分母250, 设 S = X/250
// 则S%K = (X/250)%K = (X%(250*K))/250
// 变成先求余数再除法的形式

#include <stdio.h>

// 求 (x^exp)%p 的值  O(LOG(exp))
int ExpMod(int x, int exp, int p) {
     if( exp==0 ) {
          return 1;
     }
     long long ret = ExpMod(x, exp>>1, p);
     ret = (ret*ret)%p;
     if( exp & 1 ) {
          ret = (ret*x)%p;
     }
     return (int)ret;
}

int main() {
     int N, K;
     while( scanf("%d %d", &N, &K), N && K ) {
          long long M = ExpMod(251, N+1, 250*K);
          M = (M+250*K-1)%(250*K);          // M--;

          long long M2 = ExpMod(2, 3*N+1, 250*K);
          M2 = (M2+250*K-1)%(250*K);          // M--;

          M = (M*M2)%(250*K);
          M /= 250;

          printf("%d\n", ExpMod(2008, M, K));
     }

     return 0;
}

 


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。