2010-1102

从 Trac 迁移的文章

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

原文章内容如下：

== 题意 ==
求满足以下两个条件，长度为n的b进制数的个数分别是多少
 1. x移除s~t(3<=s<=t<=n)位之间的某一位得到y，使得x % y == 0
 1. x移除最左边的一位得到y，使得x % y == 0

== 思路 ==

=== 第一问 ===
对于第一问，我们可以证明必然有 x = by，否则必然存在 x = ky (k >= b + 1 或 k <= b - 1)，设x = a,,0,,b^0^ + a,,1,,b^1^ + ... + a,,n-1,,b^n-1^ ,则 y = a,,0,,b^0^ + a,,1,,b^1^ + ... + a,,n-k-1,,b^n-k-1^ + a,,n-k+1,,b^n-k^ + ... + a,,n-1,,b^n-2^ ，若k = b + 1， 则by = a,,0,,b^0^ + (a,,0,, + a,,1,,)b^1^ + ... + (a,,n-k-2,, + a,,n-k-1,,)b^n-k-1^ + (a,,n-k-1,, + a,,n-k+1,,)b^n-k^ + ... + '''(a,,n-2,, + a,,n-1,,)b^n-2^''' + a,,n-1,,b^n-1^，x中和by中，b^n-1^的系数都是a,,n-1,,，于是看b^n-2^的系数，x中这一项的系数是a,,n-2,,而by中这一项的系数是(a,,n-2,, + a,,n-1,,) > a,,n-2,,，所以 by > x，同理也可以得出当k <= b - 1时 by < x，所以k只有等于b这一种可能。

有了这个结论，剩下的就简单了，比对下by和x，就可以得出a,,0,, = a,,1,, = ... = a,,n-k,, = 0 这个结论，于是第一种情况的答案就是(b-1) * b^(t-2)。

=== 第二问 ===
对于第二问，a,,n-1,, * b^n-1^ = k * (a,,n-2,,b^n-2^ + ... + a,,0,,)，于是就是求将a,,n-1,,b^n-1^分解成两个数的乘积，并且两数都小于b^n-1^的方方案数，所有的分解方案减去其一个数大于等于b^n-1^的方案就可以了。

== 代码 ==
from shi哥

{{{
#!java
import java.math.*;
import java.util.*;

public class Main {
    static final int[] pl = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
    static final int pn = pl.length;
    static final int[][] ps = new int[33][pn];

    static {
        for (int i = 1; i < ps.length; ++i) {
            for (int j = 0; j < pl.length; ++j) {
                int k = i;
                while (k % pl[j] == 0) {
                    ++ps[i][j];
                    k /= pl[j];
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int b = in.nextInt();
            int s = in.nextInt();
            int t = in.nextInt();

            System.out.print(BigInteger.valueOf(b).pow(t - 2).multiply(BigInteger.valueOf(b - 1)));

            BigInteger ans = BigInteger.ZERO;
            for (int i = 1; i < b; ++i) {
                int[] a = new int[pn];
                BigInteger tmp = BigInteger.ONE;

                for (int j = 0; j < pn; ++j) {
                    a[j] = ps[i][j] + ps[b][j] * (n - 1);
                    tmp = tmp.multiply(BigInteger.valueOf(a[j] + 1));
                }

                int dif = i;
                for (int k = 1; k <= i; ++k) {
                    for (int j = 0; j < pn; ++j) {
                        if (ps[k][j] > a[j]) {
                            --dif;
                            break;
                        }
                    }
                }

                ans = ans.add(tmp.subtract(BigInteger.valueOf(dif)));
            }

            System.out.println(" " + ans);
        }
    }
}
}}}

题意

求满足以下两个条件，长度为n的b进制数的个数分别是多少

1. x移除s~t(3<=s<=t<=n)位之间的某一位得到y，使得x % y == 0

1. x移除最左边的一位得到y，使得x % y == 0

思路

第一问

对于第一问，我们可以证明必然有 x = by，否则必然存在 x = ky (k >= b + 1 或 k <= b - 1)，设x = a₀b⁰ + a₁b¹ + ... + a_n-1b^n-1 ,则 y = a₀b⁰ + a₁b¹ + ... + a_n-k-1b^n-k-1 + a_n-k+1b^n-k + ... + a_n-1b^n-2 ，若k = b + 1， 则by = a₀b⁰ + (a₀ + a₁)b¹ + ... + (a_n-k-2 + a_n-k-1)b^n-k-1 + (a_n-k-1 + a_n-k+1)b^n-k + ... + (a_n-2 + a_n-1)b^n-2 + a_n-1b^n-1，x中和by中，b^n-1的系数都是a_n-1，于是看b^n-2的系数，x中这一项的系数是a_n-2而by中这一项的系数是(a_n-2 + a_n-1) > a_n-2，所以 by > x，同理也可以得出当k <= b - 1时 by < x，所以k只有等于b这一种可能。

有了这个结论，剩下的就简单了，比对下by和x，就可以得出a₀ = a₁ = ... = a_n-k = 0 这个结论，于是第一种情况的答案就是(b-1) * b^(t-2)。

第二问

对于第二问，a_n-1 * b^n-1 = k * (a_n-2b^n-2 + ... + a₀)，于是就是求将a_n-1b^n-1分解成两个数的乘积，并且两数都小于b^n-1的方方案数，所有的分解方案减去其一个数大于等于b^n-1的方案就可以了。

代码

from shi哥

import java.math.*;
import java.util.*;
public class Main {
    static final int[] pl = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
    static final int pn = pl.length;
    static final int[][] ps = new int[33][pn];
    static {
        for (int i = 1; i < ps.length; ++i) {
            for (int j = 0; j < pl.length; ++j) {
                int k = i;
                while (k % pl[j] == 0) {
                    ++ps[i][j];
                    k /= pl[j];
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int b = in.nextInt();
            int s = in.nextInt();
            int t = in.nextInt();
            System.out.print(BigInteger.valueOf(b).pow(t - 2).multiply(BigInteger.valueOf(b - 1)));
            BigInteger ans = BigInteger.ZERO;
            for (int i = 1; i < b; ++i) {
                int[] a = new int[pn];
                BigInteger tmp = BigInteger.ONE;
                for (int j = 0; j < pn; ++j) {
                    a[j] = ps[i][j] + ps[b][j] * (n - 1);
                    tmp = tmp.multiply(BigInteger.valueOf(a[j] + 1));
                }
                int dif = i;
                for (int k = 1; k <= i; ++k) {
                    for (int j = 0; j < pn; ++j) {
                        if (ps[k][j] > a[j]) {
                            --dif;
                            break;
                        }
                    }
                }
                ans = ans.add(tmp.subtract(BigInteger.valueOf(dif)));
            }
            System.out.println(" " + ans);
        }
    }
}