richard-desktop

完整的题目描述在这里。

题目给出了n和m，要求出满足最大公约数(x₁,x₂,...,x_n,m)=1且x_i不超过m的这样的x₁,...,x_n的组数。x_i都是正整数。

如果n=1，那就是求欧拉函数。我们可以联想其形式：。那么当n>1时我们也来类比一下相对应的公式。

令表示题目中所要求的答案。我们发现，当m为素数时，。这是显然的，因为除了(m,m,...,m,m)这一组数字以外，其余的都是可行的解。那么m不为素数时，我们把m的各个素因数分开考虑。如果某个素因数被n个数所共有，那么一共就少了种方案，考察m所有的素因数，我们得到。

至此，问题解决。

题目描述在这里。

题目的意思就是给定一个正整数n（n不超过9*10¹⁴），要求我们给出有多少种方式，使得n能够表示为若干个连续正整数的和。比如n=9，那么有3种方式：2+3+4，4+5，9。

我们可以假定a+(a+1)+...+(b-1)+b=n，也就是(b+a)*(b-a+1)=2n。而(b+a)+(b-a+1)=2b+1是一个奇数，说明(b+a)和(b-a+1)具有不同的奇偶性，必然有一个是奇数。我们先把n当中所有素因数2从等式两边约去，同时考虑到(b+a)和(b-a+1)奇偶性不同，就可以把问题转化为n的奇数约数有多少个。由于这里的a和b是不受n的限制的变量，我们只要得到一个奇数约数必然可以求出相应的a和b（注意到(b+a)-(b-a+1)=2a-1是一个正整数，所以(b+a)>(b-a+1)。）。比如n=12，给出一个奇数约数3，那么a=3，b=5；给出一个奇数约数1，那么a=b=12。

现在我们所要做的就是对n进行质因数分解，然后用各个素因数的指数求解。显然，O(n^1/2)的算法是不够的。我们要具体考察一下素因数分解的过程。如果用[2,L]以内的素数进行分解，那么约去所有因数后，最后剩下的n'一定不含有该范围的任何质数，也就是说n'如果小于L²，那么一定是素数；如果大于L²，那么只需要判断n'到底是不是素数。我们注意到，如果n'不是素数且只含有两个素因数，我们是可以分析出结果的，也就是说，我们需要排除n'含有三个素因数的情况。注意到(10⁵)³略大于9*10¹⁴，我们就找到了方法。

先预处理出[2,10⁵]范围内所有的素数，并且对n进行分解。然后按照上面的方法对分解的结果n'进行讨论，关于判断n'是否是素数，我们可以用Miller-Rabin素性测试来解决，Java中可以借助BigInteger的isProbablePrime来判断。整个算法的复杂度约为O(n^1/3)，下面就是代码，UVa上面的提交结果是运行了0.556s： 

import java.math.*;
import java.util.*;

class Main {
  private final static int MAXP = 100000;
  private final static long LIMIT = (long)MAXP*MAXP;
  private static int[] primes;

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    getprimes();
    while (in.hasNextLong()) {
      long n = in.nextLong();
      System.out.println(solve(n));
    }
  }

  private static int solve(long n) {
    if (n==0) return 0;
    while ((n&1)==0) n >>= 1;
    int ans = 1;
    for (int i = 0; i<primes.length; i++) {
      long t = primes[i];
      if (t*t>n) break;
      int cnt = 0;
      while (n%primes[i]==0) {
        n /= primes[i];
        cnt++;
      }
      ans *= cnt+1;
    }
    if (n==1);
    else if (n<LIMIT || BigInteger.valueOf(n).isProbablePrime(16))
      ans *= 2;
    else {
      long tmp = (long)(Math.sqrt(n)+1e-6);
      if (tmp*tmp==n) ans *= 3;
      else ans *= 4;
    }
    return ans;
  }

  private static void getprimes() {
    boolean[] isp = new boolean[MAXP+1];
    int size = 0,ptr = 0;
    for (int i = 2; i<=MAXP; i++)
      if (!isp[i]) {
        size++;
        for (int j = 2*i; j<=MAXP; j += i)
          isp[j] = true;
      }
    primes = new int[size];
    for (int i = 2; i<=MAXP; i++)
      if (!isp[i]) primes[ptr++] = i;
  }
}

完整的题目描述在这里。

题目给了我们一些货物的价格a₁,...,a_m（不超过100000），要我们构造一种货币面值的方案x₁,...,x_n，使得所需要的纸币数量尽可能少。货币面值的方案必须满足

• x₁=1。
• 对于i<j，x_i一定是x_j的约数。

注意到不需要给出面值的方案，只是要求输出最少的张数，那么我们可以用动态规划解决。对于一个确定的方案，由于上述的性质，我们一定是用贪心的方法来付款。另外，价格不会超过100000，所以需要考虑的最大面值也是100000。对于一个面额x_i，付完款之后得到的余额是a₁%x_i,...,a_m%x_i。我们令f(i)表示用面值大于等于i的货币方案所付款所需要的纸币数量， 那么f(i)=min{f(j)+余额用i付款的张数 | i为j的约数}。具体的代码如下：

public class NewCoins {
  static final int MAXN = 100000;
  public int minCoins(int[] price) {
    int n = price.length;
    int[] f = new int[MAXN+1];
    for (int i = MAXN; i>0; i--) {
      for (int j = 0; j<n; j++)
        f[i] += price[j]/i;
      for (int j = 2*i; j<=MAXN; j += i) {
        int tmp = f[j];
        for (int k = 0; k<n; k++)
          tmp += (price[k]%j)/i;
        if (f[i]>tmp) f[i] = tmp;
      }
    }
    return f[1];
  }
}

至此，问题就解决了。

SWERC2008主页在这里：SWERC 2008 - Nuremberg。这套题目还是一贯的欧洲赛区的风格，题目大多数都可以做。

• Bring Your Own Horse：题目很长很烦，从最后的Scoreboard就可以看出来很多人因为题目描述的原因没有看出来题目的意思。题目的要求很简单，就是先求一个最小生成树，然后对于每一个询问，都用一次BFS来找到生成树中两点之间路径当中最长的边。代码量并不大，但是最快的提交也用了66分钟，完全是题目描述的问题。
• First Knight：一个非常明显的高斯消元法，如果在中国赛区应该算是容易的。
• Postal Charges：一个别出心裁的降低复杂度的题目。巧妙的用类似桶排序的方法先进行分类，然后考虑到只是进行曼哈顿距离的计算，所以可以分块求解。每一个块中不同的元素都已经预处理出到自身所在块的左下角的距离，使用乘法原理就可以解决。
  

  double calc() {
    double sum = 0.0; //总长度
    int co = 0;       //路线数量
    for (int i = 1; i<MAX; i++)
      for (int j = 1; j<MAX; j++) //i,j枚举当前的块
        for (int k = 0; k<i; k++)
          for (int l = 0; l<j; l++) { //k,l枚举当前快之前的块
            //l[i][j]表示(i,j)这个块里面所有点的该块左下角的距离之和
            //c[i][j]表示每个块中含有元素的个数
            sum += l[i][j]*c[k][l]-l[k][l]*c[i][j]+(i-k+j-l)*c[i][j]*c[k][l]; //乘法原理
            co += c[i][j]*c[k][l]; //求和
          }
    return sum/co;
  }

• Randomly-priced Tickets：题目给定了一个无向图。首先用Floyd求出两点之间的距离，然后就是要求在一条定长的路线上分配初始的预算。这个问题用动态规划很容易解决。设p(i,j)表示长度为i的路线，预算为j，能够通过的可能性，那么，边界条件是i=0时p(i,j)=1。如果一个询问的两点之间长度为d，预算为b，直接输出p(d,b)就可以了。
• The Game：博弈问题，用最大最小搜索，Alpha-Beta剪枝应该会有好的效果。
• The Merchant Guild：动态规划。首先要确定方案合法的充要条件，就是最多不超过i个商人被分配到了最后的n-i+1个位置。这样令f(k,m)为在k,...,n之间还有m个空位时的分配方案数，s(k)表示前k个位置一共有多少本地商人，g(k,m)=m+1-s(k-1)+s(k-2)，那么
  
• Toll Road：分治。题目所给的是一个树，只要DFS一次，找出最大权值的子树就可以了，用分治法会很轻松。
• Top Secret：矩阵乘法。我们依据题意构造出矩阵之后进行计算，由于这是一个循环矩阵，可以把O(n³)的算法优化至O(n²)。
• Transcribed Books：数论题。注意到对于所有的序列，。那么所有序列的的最大公约数在有解的情况下就是问题的答案。
• Wizards：数学题。详细情况请参见判断方程是否有重根。

阶乘的最后一位非零位就是n!的数值中从右到左第一个非零的数字。比如，7!=5040，那么7!的最后一位非零位就是4。一个粗略的想法是每10个数字的末尾数相乘是一个定植，那么n个连续的自然数也可以类似地转化，接着就可以求出。这个想法无疑是错误的，因为注意到2*5=10，而12*15=180，两个结果的末位非零数并不相等，所以末尾数相乘不是10个数字为一个循环。

如果要求n!末尾0的个数，就是一个非常简单的问题。因为10=2*5，我们只要求出2和5在n!的标准分解式中出现了多少次，就可以求出末尾0的个数。而又由于2出现的次数一定比5多，所以，只需要求出5出现的次数。例如，n=2005，那么5出现的次数就是401+80+16+3=500个，也就是2005!的末尾有500个0。

现在我们对n!的情况有了一个大概的认识。简单点来说，n!=2^a5^bc，这里c是所有不包含2和5的因数的乘积。显然，最后一位非零位取决于2^a-bc的最后一位。我们只要想办法求出c，n!的非零位就很容易了。注意到如果一个数字的末位如果是3,5,7,9，那么一定是c的组成部分。但是这些数字还不够，因为当2和5被提取之后，又产生了新的末位为3,5,7,9的数字，所以我们要逐次的提取2和5这两个因数，然后算出每种情况下末位为3,5,7,9的数字的数量。

回忆求2这个因数的办法，就是逐次的除以2来缩小规模。例如，当n=2005时，只含有一个因数2的数一共有1002个，含有两个因数2的数字一共有501个，……。也就是一种递归的思想，不过这里是尾递归，可以消除。下面关于如何求出末位为3,5,7,9的数字的方法就不再赘述了，直接给出代码，相信还是能够理解的。

//co2,co3,co5,co7,co9分别表示了2,3,5,7,9的个数。
static int co2,co3,co5,co7,co9;

void calc(int n) {
  if (n<=1) return;
  for (int i = n; i>0; i /= 5) {
    int p = i/10,q = i%10;
    co3 = p+(int)(q>=3);
    co5 = p+(int)(q>=5);
    co7 = p+(int)(q>=7);
    co9 = p+(int)(q>=9);
  }
  co2 += n/2;
  calc(n/2);
}

至此，问题转化为了2,3,5,7,9之间幂的关系，注意到3²ⁿ=9ⁿ，而，所以又可以转化为3的幂，下面的过程就简单多了。

其实求n!的最后一位非零位还有其它的方法，但其实也不外乎利用递归的思想提取因数，来达到化大为小的目的。有兴趣的可以去Google一下，可以找到很多资料。