2010-1067

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== Contest 1 by ACFun - Bug Races ==


'''题目大意'''[[BR]]
有两只蚂蚁和一个三维长方体，两只蚂蚁要从此长方体的一个角走到其对角，第一只蚂蚁要沿着长方体表面最短路走，另一只要走形内最短路（即对角连线），要求第一只蚂蚁所走路程长度为整数，求给定长方体最长边长度的条件下，两只蚂蚁所有符合条件路线长度的平均值，用既约分数表示。

'''解法'''[[BR]]
首先可以得知一对符合条件的路线一定与一个长方体一一对应，因此假设长方体三边长分别为a, b, c且a <= b <= c，则有(a + b) * (a + b) + c * c = t * t，其中t为正整数，c等于读入的n值。整理以上的式子，可以得到c * c = (t + a + b) * (t - a - b)。则可以对c * c做因式分解，得出每一种a + b的取值可能性，之后利用平方和公式，得出答案。需要注意的是，答案会超过长整型(64位整数)的范围，可以使用实现了部分功能的大数模板或者java的BigInteger实现。
另外，标程的做法是提前预处理，这样的程序大致需要4秒左右，而直接运算需要870毫秒。

'''未做预处理的java代码'''
{{{
#!java
import java.util.*;
import java.math.*;
import java.io.*;

class BugRaces{
    static int MAXN = 1000000;
    static int[] minp = new int[1000001], plist = new int[1000001], p0 = new int[5000], p1 = new int[5000];
    static long tmp, tmpa, tmpb, N, low, high;
    static BigInteger[] A = new BigInteger[2];
    static BigInteger B, H, L, g;
    static int prime() {
        int num = 0;
        for(int i = 0;i <= MAXN;i++) minp[i] = 0;
        for (int i = 2; i <= MAXN; i++) {
            if (minp[i] == 0){
                plist[num++] = i;
                minp[i] = i;
            }
            for (int j = 0; j < num && i * plist[j] <= MAXN; j++) {
                minp[i * plist[j]] = plist[j];
                if (i % plist[j] == 0) break;
            }
        }
        return num;
    }
    static int factorize(int n) {
        int num = 0;
        while (n != 1) {
            if(num == 0 || minp[n] != p0[num - 1]){
                p0[num] = minp[n];
                p1[num++] = 2;
            }else{
                p1[num - 1] += 2;
            }
            n /= minp[n];
        }
        return num;
    }
    static void calc(int dep, long val){
        if(val <= N){
            if(dep > 0){
                calc(dep - 1, val);
                for(int i = 0;i < p1[dep - 1];i++){
                    val *= p0[dep - 1];
                    if(val > N) return;
                    calc(dep - 1, val);
                }
            }else{
                tmp = N * N / val;
                if((tmp & 1) != (val & 1)) return;
                tmpa = (tmp + val) >> 1;
                tmpb = (tmp - val) >> 1;
                if(tmpb <= (N << 1)){
                    low = Math.max(1, tmpb - N) - 1;
                    high = Math.min(N, tmpb >> 1);
                    if(low < high){
                        H = BigInteger.valueOf(high); L = BigInteger.valueOf(low);
                        B = B.add(H.subtract(L));
                        A[0] = A[0].add(BigInteger.valueOf(tmpa).multiply(BigInteger.valueOf(tmpa)).multiply(H.subtract(L)));
                        A[1] = A[1].add(BigInteger.valueOf(N).multiply(BigInteger.valueOf(N)).multiply(H.subtract(L)));
                        A[1] = A[1].add((H.multiply(H.add(BigInteger.ONE)).shiftRight(1)).multiply(H.add(H).add(BigInteger.ONE)).divide(BigInteger.valueOf(3)));
                        A[1] = A[1].subtract((L.multiply(L.add(BigInteger.ONE)).shiftRight(1)).multiply(L.add(L).add(BigInteger.ONE)).divide(BigInteger.valueOf(3)));
                        low = tmpb - low - 1;
                        high = tmpb - high - 1;
                        H = BigInteger.valueOf(high); L = BigInteger.valueOf(low);
                        A[1] = A[1].subtract((H.multiply(H.add(BigInteger.ONE)).shiftRight(1)).multiply(H.add(H).add(BigInteger.ONE)).divide(BigInteger.valueOf(3)));
                        A[1] = A[1].add((L.multiply(L.add(BigInteger.ONE)).shiftRight(1)).multiply(L.add(L).add(BigInteger.ONE)).divide(BigInteger.valueOf(3)));
                    }
                }
            }
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        prime();
        while(sc.hasNextInt()){
            N = sc.nextInt();
            int dep = factorize((int)N);
            A[0] = A[1] = B = BigInteger.ZERO;
            calc(dep, 1);
            if(B.equals(BigInteger.ZERO))
                System.out.println("NaN NaN");
            else for(int i = 0;i < 2;i++){
                g = A[i].gcd(B);
                System.out.print(A[i].divide(g) + "/" + B.divide(g));
                if(i == 0) System.out.print(" "); else System.out.println();
            }
        }
    }
}
}}}

'''watashi的标准程序'''
{{{
#!cpp
#include <cstdio>
#include <vector>
#include <utility>
#include <cassert>
#include <algorithm>

using namespace std;

const int LIMIT = 1000001;
const int RLIMIT = 1600;

template<typename T>
inline T gcd(T a, T b) {
    return b == 0 ? a : gcd(b, a % b);
}

struct BigInt {
    static const long long MOD = 1000000000000000000LL;
    long long h, l;

    BigInt() : h(0), l(0) {
    }

    void add(long long x) {
        l += x;
        while (l >= MOD) {
            l -= MOD;
            ++h;
        }
    }

    void print(long long x) {
        if (x == 0) {
            printf("NaN");
            return;
        }
        long long g = gcd((h % x) * (MOD % x) + l, x);
        long long hh = h / g;
        long long ll = (h % g) * (MOD / g) + ((h % g) * (MOD % g) + l) / g;
        if (hh > 0) {
            printf("%lld%018lld/%lld", hh, ll, x / g);
        } else {
            printf("%lld/%lld", ll, x / g);
        }
    }
};

// r=first; s=second
// x=r^2-s^2; y=2rs; z=r^2+s^2
// vector<pair<int, int> > pythagoras;
// static BigInt a[LIMIT];
// static BigInt b[LIMIT];
// static long long c[LIMIT];

static struct ABC {
    BigInt a, b;
    long long c;
} abc[LIMIT];


inline long long sum2(long long n) {    // \sum_{i=0}^n{i^2}
    return n * (n + 1) / 2 * (n + n + 1) / 3;
}

inline void gao(long long x, long long y) {
    long long l = max(1LL, x - y);
    long long r = x / 2 + 1;
    if (l < r) {
        abc[y].a.add((x * x + y * y) * (r - l));
        abc[y].b.add(sum2(r - 1) - sum2(l - 1));
        abc[y].b.add(sum2(x - l) - sum2(x - r));
        abc[y].b.add((y * y) * (r - l));
        abc[y].c += r - l;
    }
}

void init() {
    // pythagoras
    for (int r = 1; r < RLIMIT; ++r) {
        for (int s = r % 2 + 1; s < r; s += 2) {
            if (gcd(r, s) == 1) {
                int x = r * r - s * s;
                int y = 2 * r * s;
                if (x > y) {
                    swap(x, y);
                }
                for (long long i = x, j = y; i < LIMIT; i += x, j += y) {
                //  pythagoras.push_back(make_pair(i, j));
                    if (j < LIMIT) {
                        gao(i, j);
                    }
                    gao(j, i);
                }
            }
        }
    }
    // printf("%d\n", pythagoras.size());   // 2388959
}

int main() {
    int n = 0;

    init();
    while (scanf("%d", &n) != EOF) {
        assert(1 <= n && n <= 1000000);
        abc[n].a.print(abc[n].c);
        putchar(' ');
        abc[n].b.print(abc[n].c);
        puts("");
    }

    return 0;
}
}}}

Contest 1 by ACFun - Bug Races

题目大意

有两只蚂蚁和一个三维长方体，两只蚂蚁要从此长方体的一个角走到其对角，第一只蚂蚁要沿着长方体表面最短路走，另一只要走形内最短路（即对角连线），要求第一只蚂蚁所走路程长度为整数，求给定长方体最长边长度的条件下，两只蚂蚁所有符合条件路线长度的平均值，用既约分数表示。

解法

首先可以得知一对符合条件的路线一定与一个长方体一一对应，因此假设长方体三边长分别为a, b, c且a <= b <= c，则有(a + b) * (a + b) + c * c = t * t，其中t为正整数，c等于读入的n值。整理以上的式子，可以得到c * c = (t + a + b) * (t - a - b)。则可以对c * c做因式分解，得出每一种a + b的取值可能性，之后利用平方和公式，得出答案。需要注意的是，答案会超过长整型(64位整数)的范围，可以使用实现了部分功能的大数模板或者java的BigInteger实现。

另外，标程的做法是提前预处理，这样的程序大致需要4秒左右，而直接运算需要870毫秒。

未做预处理的java代码

import java.util.*;
import java.math.*;
import java.io.*;
class BugRaces{
    static int MAXN = 1000000;
    static int[] minp = new int[1000001], plist = new int[1000001], p0 = new int[5000], p1 = new int[5000];
    static long tmp, tmpa, tmpb, N, low, high;
    static BigInteger[] A = new BigInteger[2];
    static BigInteger B, H, L, g;
    static int prime() {
        int num = 0;
        for(int i = 0;i <= MAXN;i++) minp[i] = 0;
        for (int i = 2; i <= MAXN; i++) {
            if (minp[i] == 0){
                plist[num++] = i;
                minp[i] = i;
            }
            for (int j = 0; j < num && i * plist[j] <= MAXN; j++) {
                minp[i * plist[j]] = plist[j];
                if (i % plist[j] == 0) break;
            }
        }
        return num;
    }
    static int factorize(int n) {
        int num = 0;
        while (n != 1) {
            if(num == 0 || minp[n] != p0[num - 1]){
                p0[num] = minp[n];
                p1[num++] = 2;
            }else{
                p1[num - 1] += 2;
            }
            n /= minp[n];
        }
        return num;
    }
    static void calc(int dep, long val){
        if(val <= N){
            if(dep > 0){
                calc(dep - 1, val);
                for(int i = 0;i < p1[dep - 1];i++){
                    val *= p0[dep - 1];
                    if(val > N) return;
                    calc(dep - 1, val);
                }
            }else{
                tmp = N * N / val;
                if((tmp & 1) != (val & 1)) return;
                tmpa = (tmp + val) >> 1;
                tmpb = (tmp - val) >> 1;
                if(tmpb <= (N << 1)){
                    low = Math.max(1, tmpb - N) - 1;
                    high = Math.min(N, tmpb >> 1);
                    if(low < high){
                        H = BigInteger.valueOf(high); L = BigInteger.valueOf(low);
                        B = B.add(H.subtract(L));
                        A[0] = A[0].add(BigInteger.valueOf(tmpa).multiply(BigInteger.valueOf(tmpa)).multiply(H.subtract(L)));
                        A[1] = A[1].add(BigInteger.valueOf(N).multiply(BigInteger.valueOf(N)).multiply(H.subtract(L)));
                        A[1] = A[1].add((H.multiply(H.add(BigInteger.ONE)).shiftRight(1)).multiply(H.add(H).add(BigInteger.ONE)).divide(BigInteger.valueOf(3)));
                        A[1] = A[1].subtract((L.multiply(L.add(BigInteger.ONE)).shiftRight(1)).multiply(L.add(L).add(BigInteger.ONE)).divide(BigInteger.valueOf(3)));
                        low = tmpb - low - 1;
                        high = tmpb - high - 1;
                        H = BigInteger.valueOf(high); L = BigInteger.valueOf(low);
                        A[1] = A[1].subtract((H.multiply(H.add(BigInteger.ONE)).shiftRight(1)).multiply(H.add(H).add(BigInteger.ONE)).divide(BigInteger.valueOf(3)));
                        A[1] = A[1].add((L.multiply(L.add(BigInteger.ONE)).shiftRight(1)).multiply(L.add(L).add(BigInteger.ONE)).divide(BigInteger.valueOf(3)));
                    }
                }
            }
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        prime();
        while(sc.hasNextInt()){
            N = sc.nextInt();
            int dep = factorize((int)N);
            A[0] = A[1] = B = BigInteger.ZERO;
            calc(dep, 1);
            if(B.equals(BigInteger.ZERO))
                System.out.println("NaN NaN");
            else for(int i = 0;i < 2;i++){
                g = A[i].gcd(B);
                System.out.print(A[i].divide(g) + "/" + B.divide(g));
                if(i == 0) System.out.print(" "); else System.out.println();
            }
        }
    }
}

watashi的标准程序

#include <cstdio>
#include <vector>
#include <utility>
#include <cassert>
#include <algorithm>
using namespace std;
const int LIMIT = 1000001;
const int RLIMIT = 1600;
template<typename T>
inline T gcd(T a, T b) {
    return b == 0 ? a : gcd(b, a % b);
}
struct BigInt {
    static const long long MOD = 1000000000000000000LL;
    long long h, l;
    BigInt() : h(0), l(0) {
    }
    void add(long long x) {
        l += x;
        while (l >= MOD) {
            l -= MOD;
            ++h;
        }
    }
    void print(long long x) {
        if (x == 0) {
            printf("NaN");
            return;
        }
        long long g = gcd((h % x) * (MOD % x) + l, x);
        long long hh = h / g;
        long long ll = (h % g) * (MOD / g) + ((h % g) * (MOD % g) + l) / g;
        if (hh > 0) {
            printf("%lld%018lld/%lld", hh, ll, x / g);
        } else {
            printf("%lld/%lld", ll, x / g);
        }
    }
};
// r=first; s=second
// x=r^2-s^2; y=2rs; z=r^2+s^2
// vector<pair<int, int> > pythagoras;
// static BigInt a[LIMIT];
// static BigInt b[LIMIT];
// static long long c[LIMIT];
static struct ABC {
    BigInt a, b;
    long long c;
} abc[LIMIT];
inline long long sum2(long long n) {    // \sum_{i=0}^n{i^2}
    return n * (n + 1) / 2 * (n + n + 1) / 3;
}
inline void gao(long long x, long long y) {
    long long l = max(1LL, x - y);
    long long r = x / 2 + 1;
    if (l < r) {
        abc[y].a.add((x * x + y * y) * (r - l));
        abc[y].b.add(sum2(r - 1) - sum2(l - 1));
        abc[y].b.add(sum2(x - l) - sum2(x - r));
        abc[y].b.add((y * y) * (r - l));
        abc[y].c += r - l;
    }
}
void init() {
    // pythagoras
    for (int r = 1; r < RLIMIT; ++r) {
        for (int s = r % 2 + 1; s < r; s += 2) {
            if (gcd(r, s) == 1) {
                int x = r * r - s * s;
                int y = 2 * r * s;
                if (x > y) {
                    swap(x, y);
                }
                for (long long i = x, j = y; i < LIMIT; i += x, j += y) {
                //  pythagoras.push_back(make_pair(i, j));
                    if (j < LIMIT) {
                        gao(i, j);
                    }
                    gao(j, i);
                }
            }
        }
    }
    // printf("%d\n", pythagoras.size());   // 2388959
}
int main() {
    int n = 0;
    init();
    while (scanf("%d", &n) != EOF) {
        assert(1 <= n && n <= 1000000);
        abc[n].a.print(abc[n].c);
        putchar(' ');
        abc[n].b.print(abc[n].c);
        puts("");
    }
    return 0;
}