UVa 1635 - Irrelevant Elements(二项式系数 + 唯一分解定理)

时间:2021-09-10 15:14:43

链接:

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4510

题意:

对于给定的n个数a1, a2,…, an,依次求出相邻两数之和,将得到一个新数列。重复上述操作,最后结果将变成一个数。
问这个数除以m的余数与哪些数无关?例如n=3,m=2时,第一次求和得到a1+a2,a2+a3,
再求和得到a1+2a2+a3,它除以2的余数和a2无关。1≤n≤1e5,2≤m≤1e9。

分析:

不难证明,在一般情况下,最后ai的系数是C(n-1,i-1)。这样,问题就变成了求C(n-1,0), C(n-1,1), ...,C(n-1,n-1)中
有哪些是m的倍数。理论上,利用C(n,k) = (n-k+1)/k * C(n,k-1)可以递推出所有C(n-1,i-1),但它们太大了,
虽然可以用高精度,但是运算会很慢。然而此问题中所关心的只是“哪些是m的倍数”,所以只需要依次计算m的
唯一分解式中各个素因子在C(n-1,i-1)中的指数即可完成判断。这些指数仍然可以用上式递推,并且不会涉及高精度。

代码:

 import java.io.*;
import java.util.*; public class Main {
static ArrayList<Integer> prime = new ArrayList<Integer>(); static void resolve(int m) {
int u = (int)Math.sqrt(m + 0.5);
for(int i = 2; i <= u; i++) {
if(m % i != 0) continue;
prime.add(i);
while(m % i == 0) m /= i;
}
if(m > 1) prime.add(m);
} public static void main(String args[]) {
Scanner cin = new Scanner(new BufferedInputStream(System.in)); while(cin.hasNext()) {
int n = cin.nextInt();
int m = cin.nextInt(); n--;
boolean bad[] = new boolean[n+5];
prime.clear();
resolve(m);
for(int t = 0; t < prime.size(); t++) { // 求C(n,0)~C(n,n)有哪些数是m的倍数
int p = prime.get(t), e = 0, x = m, min = 0; // C(n,i) = p^e
while(x % p == 0) { x /= p; min++; }
for(int k = 1; k < n; k++) { // C(n,k)=C(n,k-1)*(n-k+1)/k
x = n - k + 1;
while(x % p == 0) { x /= p; e++; }
x = k;
while(x % p == 0) { x /= p; e--; }
if(e < min) bad[k] = true;
}
} ArrayList<Integer> ans = new ArrayList<Integer>();
for(int i = 1; i < n; i++) if(!bad[i]) ans.add(i+1);
System.out.println(ans.size());
if(ans.size() > 0) {
System.out.print(ans.get(0));
for(int i = 1; i < ans.size(); i++)
System.out.print(" " + ans.get(i));
}
System.out.println();
}
cin.close();
}
}