第48次编程比赛结果 — 编程爱好者社区

用户id          通过测试数(重复100次的时间):结果错误数:运行错误数
                第一题           第二题
neverPE:        101(16 ms):0:0   7(112 ms):0:0
ldb2741:        101(3515 ms):0:0 4(0 ms):97:0
rj1985:         101(62 ms):0:0   4(0 ms):97:0
dongch007:      101(188 ms):0:0  4(15 ms):97:0
user_09:        101(47 ms):0:0   4(0 ms):97:0
bpttc:          101(47 ms):0:0   3(0 ms):98:0
argentmoon:     101(47 ms):0:0   1(0 ms):100:0
zy1121:         101(63 ms):0:0   0(0 ms):101:0
user_06:        101(78 ms):0:0   0(0 ms):101:0
songfei:        101(3484 ms):0:0 0(0 ms):101:0
marry3640:      101(3750 ms):0:0 0(0 ms):101:0
bpttc2:         55(0 ms):46:0    3(32 ms):98:0
bloodybg:       40(374 ms):61:0  0(0 ms):101:0
hotzenplotz:    8(0 ms):93:0     0(0 ms):101:0
qqlxinye:       7(110 ms):94:0   0(0 ms):101:0

wshong 测试时间过长，被终止...
skybtone 测试中申请内存数量巨大且不释放，测试过程中由于内存申请导致虚拟内存不足死机状- -。后来

终于被我制服。提醒后人测试前至少粗略阅读一下被测代码以免受同样遭遇。

neverPE代码中可能是笔误把continue写成了break，改为continue后完全通过。其他代码有部分修改以便配

合编译器和测试环境（包括接口定义统一化，去除临时输出等）。

这次题目其实有些难度，如果误以为直接按题目所说的计算就可以就上当了。算法neverPE已经说出来了。
推倒过程略。

本次获胜者为neverPE，有请neverPE准备49次比赛:)并发表获奖感言～

附上我的代码，速度上没有neverPE的快，呵呵:(
[code]
#include <cstdio>
#include <cassert>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

namespace kaikai
{

static vector<int> primes;
bool IsPrime(int n)
{
     for(size_t i = 0; primes[i] * primes[i] <= n; i++)
     {
          if (n % primes[i] == 0)
               return false;
     }
     return true;
}

int GetPrime(size_t index)
{
     assert(index < 10000);

     if (index >= primes.size())
     {
          if (primes.size() == 0)
          {
               primes.reserve(10000);
               primes.push_back(2);
               primes.push_back(3);
               primes.push_back(5);
               primes.push_back(7);
          }
          for (int t = primes.back() + 2; index >= primes.size(); t += 2)
          {
               if (IsPrime(t))
                    primes.push_back(t);
          }
     }

     return primes[index];
}
int SumFactorMod(int n, int m, int s)
{
     vector<pair<int, size_t> > factors;
     int t;
     for(t = 0; n > 1; t++)
     {
          pair<int, size_t> factor(GetPrime(t), 0);
          while(n % factor.first == 0)
               n /= factor.first, factor.second++;
          if (factor.second)
               factors.push_back(factor);
     }
     int sum = 1;
     for (t = 0; t < factors.size(); t++)
     {
          const pair<int, size_t> &factor = factors[t];
          int d = 0, q = 1, maxi = factor.second * m;
          for (size_t i = 0; i <= maxi; i++)
          {
               d += q;
               d %= s;
               q *= factor.first;
               q %= s;
          }
          sum *= d;
          sum %= s;
     }
     return sum % s;
}
int SumFactorMod(int n, int s)
{
     return SumFactorMod(n, 1, s);
}
}
[/code]
附上测试代码：
[code]
#include <windows.h>
class Test
{
public:
     struct TestCase
     {
          int n, m, s;
          int out1, out2;
     };
     struct Testee
     {
          Testee():pF1(0), pF2(0), score1(0), score2(0),
               wa1(0), wa2(0), wte1(0), wte2(0), time1(0), time2(0)
          {
          }
          int (*pF1)(int n, int s);
          int (*pF2)(int n, int m, int s);
          int score1, score2;
          int wa1, wa2;
          int wte1, wte2;
          int time1, time2;
          string name;
          bool operator < (const Testee &o) const
          {
               if (score1 == o.score1)
                    return time1 + time2 < o.time1 + o.time2;
               return score1 > o.score1;
          }
     };
     void AddTestee(int (*pF1)(int n, int s), int (*pF2)(int n, int m, int s), const char

*name)
     {
          Testee testee;
          testee.pF1 = pF1;
          testee.pF2 = pF2;
          testee.name = name;
          testees.push_back(testee);
     }
     void AddTestCase(int n, int m, int s)
     {
          TestCase tc;
          tc.n = n;
          tc.m = m;
          tc.s = s;
          tc.out1 = GetSumOfFactor(n, 1, s);
          tc.out2 = GetSumOfFactor(n, m, s);
          testCases.push_back(tc);
     }
     void go()
     {
          for (int i = 0; i < testees.size(); i++)
          {
               Testee &testee = testees[i];
               printf("Testing %s", testee.name.c_str());
               for (int j = 0; j < testCases.size(); j++)
               {
                    if (j % 10 == 9)
                         printf(".");
                    const TestCase &testCase = testCases[j];
                    int o1 = -1, o2 = -1;
                    //printf("\n%d,%d,%d (%d %d)\n", testCase.n, testCase.m,

testCase.s, testCase.out1, testCase.out2);
                    try
                    {
                         DWORD t1 = GetTickCount();
                         for (int k = 0; k < 25; k++)
                         {
                              o1 = testee.pF1(testCase.n, testCase.s);
                              o1 = testee.pF1(testCase.n, testCase.s);
                              o1 = testee.pF1(testCase.n, testCase.s);
                              o1 = testee.pF1(testCase.n, testCase.s);
                         }
                         DWORD t2 = GetTickCount();
                         if (o1 == testCase.out1)
                         {
                              testee.score1++;
                              testee.time1 += t2 - t1;
                         }
                         else
                         {
                              testee.wa1++;
                              //printf("o1 = %d\n", o1);
                         }
                    }
                    catch (...)
                    {
                         testee.wte1++;
                    }
                    try
                    {
                         DWORD t1 = GetTickCount();
                         for (int k = 0; k < 25; k++)
                         {
                              o2 = testee.pF2(testCase.n, testCase.m,

testCase.s);
                              o2 = testee.pF2(testCase.n, testCase.m,

testCase.s);
                              o2 = testee.pF2(testCase.n, testCase.m,

testCase.s);
                              o2 = testee.pF2(testCase.n, testCase.m,

testCase.s);
                         }
                         DWORD t2 = GetTickCount();
                         if (o2 == testCase.out2)
                         {
                              testee.score2++;
                              testee.time2 += t2 - t1;
                         }
                         else
                         {
                              testee.wa2++;
                              //printf("o2 = %d\n", o1);
                         }
                    }
                    catch (...)
                    {
                         testee.wte2++;
                    }
               }
               printf("\n");
          }
          sort(testees.begin(), testees.end());
          for (int i = 0; i < testees.size(); i++)
          {
               Testee &testee = testees[i];
               printf("%s:\t%d(%dms):%d:%d\t%d(%dms):%d:%d\n", testee.name.c_str(),
                    testee.score1, testee.time1, testee.wa1, testee.wte1,
                    testee.score2, testee.time2, testee.wa2, testee.wte2);
          }
     }
     vector<Testee> testees;
     vector<TestCase> testCases;
};
Test test;
#define TESTEE(a) test.AddTestee(a::SumFactorMod, a::SumFactorMod, #a)

int main()
{
     TESTEE(ldb2741);
     TESTEE(qqlxinye);
     TESTEE(user_06); // 雪光风剑
     // TESTEE(skybtone);  //内存爆裂弹- -
     TESTEE(user_09);// 独行者
     // TESTEE(wshong); // 疑似死循环
     TESTEE(bloodybg);
     TESTEE(bpttc);
     TESTEE(bpttc2);
     TESTEE(rj1985);
     TESTEE(marry3640);
     TESTEE(dongch007);
     TESTEE(argentmoon);
     TESTEE(songfei);
     TESTEE(hotzenplotz);
     TESTEE(zy1121);
     TESTEE(neverPE);
     //TESTEE(kaikai);

     test.AddTestCase(93, 113, 100);
     test.AddTestCase(93, 116, 7);
     srand(GetTickCount());
     for (int i = 0; i < 99; i++)
     {
          test.AddTestCase(rand() % 5000000, rand() % 5000000, rand() % 4999999+1);
     }
     test.go();
     return 0;
}
[/code]

整理一下：
[code]
#include <cassert>
#include <vector>
using namespace std;

static vector<int> primes;
bool IsPrime(int n)
{
     for(size_t i = 0; primes[i] * primes[i] <= n; i++)
     {
          if (n % primes[i] == 0)
               return false;
     }
     return true;
}

int GetPrime(size_t index)
{
     assert(index < 10000);

     if (index >= primes.size())
     {
          if (primes.size() == 0)
          {
               primes.reserve(10000);
               primes.push_back(2);
               primes.push_back(3);
               primes.push_back(5);
               primes.push_back(7);
          }
          for (int t = primes.back() + 2; index >= primes.size(); t += 2)
          {
               if (IsPrime(t))
                    primes.push_back(t);
          }
     }

     return primes[index];
}

__int64 PowerMod(__int64 n, __int64 m, __int64 s)
{
    __int64 t;
    for(t = 1; m; m >>= 1)
    {
        if (m & 1)
            t = t * n % s;
        n = n * n % s;
    }
    return t;
}

int SumFactorMod(int n, int m, int s)
{
     int t;
     int sum = 1;
     for(t = 0; n > 1; t++)
     {
          int p = GetPrime(t);
          int q = 0;
          while(n % p == 0)
               n /= p, q++;
          if (q)
          {
/*
若 n = PI{pi^qi}   pi为质数，则有sum = PI{ f(pi, qi) }
f(p, q) = p^0 + p^1 + P^2 + ... p^q  = (p^(q+1) - 1) / (p-1)
sum % s = PI{ f(pi, qi) % s } % s
f(p, q) % s = (p^(q+1) - 1) / (p-1) % s
由x/y%z = x%(y*z)/y得到
f(p, q) % s = (p^(q+1) - 1) % (s * (p-1)) / (p-1)
= (p^(q+1) % (s*(p-1)) + (s*(p-1)-1)) % s*(p-1) / (p-1)
其中 p^(q+1) % (s*(p-1)) 可以由PowerMod快速求解得到
*/
              q *= m;
              __int64 sp_1 = __int64(s)*(p - 1);
              __int64 t = PowerMod(p, q+1, sp_1);
              t += sp_1 - 1;
              sum *= t % sp_1 / (p - 1);
              sum %= s;
          }
     }
     return sum % s;
}

int SumFactorMod(int n, int s)
{
     return SumFactorMod(n, 1, s);
}
[/code]

主题：第48次编程比赛结果

回复列表（共21个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖