zoj 3665 – Yukari’s Birthday

这道题本身不难想到方法,但时间卡的很死,因此在一些效率和精度的问题上耗费了相当的时间。

问题:

  1. 给出一个数 n,将其表示成一个等比数列 (n | n-1) = (k + k^2 + … + k^r),输出使得 r * k 最小的 r,如果有多个最优结果,取 r 较小的结果。

想法很简单:

  1. 可以想到一个最差的结果就是 (r = 1, k = n-1),这是一个只有一项的等比数列;
  2. 由于给的 n <= 10^12 < 2^40,因此 r 的取值不会超过 40;
  3. 如果知道 r,则可以用二分查找试图找到 k;
  4. 在 r 已知的情况下,k 的取值大于 2,小于 n^(1/r),因为 n = k^r + … + 1 < k^r。

因此,枚举 r,二分 k,但由于时间真的卡的比较死,因此二分 k 的时候 k 的初值就变成了瓶颈,开始使用 Python 写的很爽,但是 TLE,无奈之下改用 C++,但又遇上该死的溢出问题,而且效率依然有瓶颈。最终正式在 C++ 代码中认认真真把溢出判断写好了,把时间压缩好,才终于过了。回过头优化 Python 的代码效率,也居然可以过了。

下面是代码:

# -*- coding: utf8 -*-
import sys

# 3487680 2013-12-08 20:56:03 Accepted 3665 Python 960 140 呆滞的慢板

# 寻找前 n 项和为 s 或 s-1 的等比数列的公比,失败返回 0。
def find_q(s, n):
    # r 的初值是效率的瓶颈!
    l, r = 1, int(s**(1.0/n)) + 1
    while l < r - 1:
        q = l + r >> 1
        if q*(q**n-1) in (s*(q-1), (s-1)*(q-1)):
            return q
        elif q*(q**n-1) > s*(q-1):
            r = q
        else: l = q
    return 0

for line in sys.stdin:
    n = int(line)
    a = (1, n - 1)
    for r in range(2, 41):
        q = find_q(n, r)
        if q and r * q < a[0] * a[1]:
            a = (r, q)
    print a[0], a[1]
// 3487620 2013-12-08 15:14:16 Accepted 3665 C++ 210 272 呆滞的慢板
// 1. 效率卡得很死,瓶颈在于 find_q 函数中二分上限 r 的取值。
// 2. 在 c++ 下存在溢出的问题,因此对于计算 pow 溢出的情况需要特别小心处理。 

#include<iostream> 
#include<string> 
#include<cmath> 
#include<algorithm> 
using namespace std;

typedef long long i64;

i64 i64_pow(i64 a, i64 n) {
    if(n == 0) return 1;
    i64 ans = i64_pow(a, n>>1);
    ans *= ans;
    return (n&1) ? ans * a : ans;
}

i64 find_q(i64 s, i64 n) {
    i64 l = 1, r = i64(pow(s, 1.0/n)) + 1;
    while(l < r - 1) {
        i64 q = (l + r) / 2;
        i64 pwqn = pow(double(q), double(n)) > 1e14 ? 0 : i64_pow(q, n);
        i64 ss = (pwqn-1)/(q-1)*q;
        if(pwqn && (ss == s || ss == s-1)) return q;
        else if(pwqn == 0 || ss > s) r = q;
        else l = q;
    }
    return 0;
}

int main() {

    for(i64 n; cin >> n;) {
        pair<i64, i64> a = make_pair(1, n - 1);
        for(i64 r = 2; r < 41; ++r) {
            i64 k = find_q(n, r);
            if(k && r * k < a.first * a.second)
                a = make_pair(r, k);
        }
        cout << a.first << ' ' << a.second << endl;
    }

}

【转载请附】愿以此功德,回向 >>

原文链接:http://www.huangwenchao.com.cn/2013/12/zoj3665.html【zoj 3665 – Yukari’s Birthday】

发表评论

电子邮件地址不会被公开。 必填项已用*标注