求100!的约数个数和约数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package lanqiao;
import java.util.*;
public class math0 {
    static List<Integer>primes=new LinkedList<Integer>();
    static void sPrime(int n) {
        boolean[]st=new boolean[n+1];
        for(int i=2;i<=n;i++) {
            if(!st[i])primes.add(i);
            for(int j=0;primes.get(j)*i<=n;j++) {
                st[primes.get(j)*i]=true;
                if(i%primes.get(j)==0)break;
            }
        }
    }
    static int minc(int n,int p) {
        int rxp=0;
        while(n>0) {
            n/=p;
            rxp+=n;
        }
        return rxp;
    }
    static long qui(long a,long b) {
        long res=1;
        while(b>0) {
            if((b&1)==1) {
                res*=a;
            }
            a=a*a;
            b/=2;
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int n=100;
        sPrime(n);
        int []exp=new int[primes.size()];
        for(int i=0;i<primes.size();i++) {
            int p=primes.get(i);
            exp[i]=minc(n,p);
        }
        int numy=1;
        for(int e:exp) {
            numy*=(e+1);
        }
        long sumy=1L;
        for(int i=0;i<primes.size();i++) {
            int p=primes.get(i);
            int e=exp[i];
            sumy*=(qui(p,e+1)-1)/(p-1);
        }
        System.out.println(numy+"  "+sumy);
        scan.close();
    }
}

质因数分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.HashMap;
import java.util.Map;

public class PrimeFactorization {
    public static void main(String[] args) {
        int x = 100; // 待分解的数
        Map<Integer, Integer> primeFactors = divide(x);

        // 输出质因数及其次数
        for (Map.Entry<Integer, Integer> entry : primeFactors.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
    }

    public static Map<Integer, Integer> divide(int x) {
        Map<Integer, Integer> primeFactors = new HashMap<>();

        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                int count = 0;
                while (x % i == 0) {
                    x /= i;
                    count++;
                }
                primeFactors.put(i, count);
            }
        }

        // 如果最后剩下的x > 1，说明它本身是质数
        if (x > 1) {
            primeFactors.put(x, 1);
        }

        return primeFactors;
    }
}

欧拉函数（Euler’s Totient Function）

欧拉函数 ϕ(n)ϕ(n) 表示小于或等于 n_n_ 的正整数中与 n_n_ 互质的数的个数。 性质：

  • 若 n_是质数，ϕ(n)=n−1_ϕ(n)=_n_−1。
  • 若 n=pk_n_=*pk_，ϕ(n)=pk−pk−1_ϕ_(n)=_pk_−_p*_k_−1。
  • 若 n=a×b_n_=a_×_b 且 a_a_ 和 b_b_ 互质，ϕ(n)=ϕ(a)×ϕ(b)ϕ(n)=ϕ(a)×_ϕ_(b)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class EulerTotient {
    public static int eulerTotient(int n) {
        int result = n;
        for (int p = 2; p * p <= n; p++) {
            if (n % p == 0) {
                while (n % p == 0) {
                    n /= p;
                }
                result -= result / p;
            }
        }
        if (n > 1) {
            result -= result / n;
        }
        return result;
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("欧拉函数φ(" + n + ") = " + eulerTotient(n));
    }
}

别考，求！

卢卡斯定理（Lucas Theorem）及其适用性

卢卡斯定理的表述

若 p_p_ 是质数，则对于任意整数 1≤m≤n1≤_m_≤_n_，组合数 C(n,m)C(n,m) 满足：

C(n,m)≡C(n mod p,m mod p)×C(⌊np⌋,⌊mp⌋)(modp)C(n,m)≡_C_(n_mod_p,m_mod_p)×_C_(⌊*pn_⌋,⌊_pm_⌋)(mod_p*)

其中：

  • C(n mod p,m mod p)C(n_mod_p,m_mod_p) 是 小规模组合数（直接用公式计算）。
  • C(⌊np⌋,⌊mp⌋)C(⌊*pn_⌋,⌊_pm*⌋) 是 递归计算的组合数。

适用条件

  1. p*p* 必须是质数，否则卢卡斯定理不成立。
  2. 适用于 n*n* 和 m*m* 较大的情况（如 n,m≤1018_n_,m_≤1018，但 p_p 较小）。
  3. 不适用于非质数模数（如 p=4_p_=4 或 p=109+7_p_=109+7 但非质数）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
若p是质数，则对于任意整数 1 <= m <= n，有：
    C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)

int qmi(int a, int k, int p)  // 快速幂模板
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(int a, int b, int p)  // 通过定理求组合数C(a, b)
{
    if (a < b) return 0;

    LL x = 1, y = 1;  // x是分子，y是分母
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        x = (LL)x * i % p;
        y = (LL) y * j % p;
    }

    return x * (LL)qmi(y, p - 2, p) % p;
}

int lucas(LL a, LL b, int p)
{
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

扩展卢卡斯定理（Lucas Theorem）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ExLucas {

    // 质因数分解 p = p1^k1 * p2^k2 * ... * pm^km
    public static Map<Integer, Integer> factorize(int p) {
        Map<Integer, Integer> factors = new HashMap<>();
        for (int i = 2; i * i <= p; i++) {
            while (p % i == 0) {
                factors.put(i, factors.getOrDefault(i, 0) + 1);
                p /= i;
            }
        }
        if (p > 1) factors.put(p, 1);
        return factors;
    }

    // 计算 n! 中去除 p 的因子后的值 mod p^k
    public static int factorialMod(int n, int p, int pk) {
        if (n == 0) return 1;
        int res = 1;
        for (int i = 1; i <= pk; i++) {
            if (i % p == 0) continue; // 跳过 p 的倍数
            res = (res * i) % pk;
        }
        res = powMod(res, n / pk, pk);
        for (int i = 1; i <= n % pk; i++) {
            if (i % p == 0) continue;
            res = (res * i) % pk;
        }
        return (res * factorialMod(n / p, p, pk)) % pk;
    }

    // 快速幂算法
    public static int powMod(int base, int exp, int mod) {
        int result = 1;
        base = base % mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % mod;
            }
            exp = exp >> 1;
            base = (base * base) % mod;
        }
        return result;
    }

    // 计算 n! 中 p 的幂次
    public static int countP(int n, int p) {
        int count = 0;
        while (n > 0) {
            n /= p;
            count += n;
        }
        return count;
    }

    // 计算 C(n, m) mod p^k
    public static int combModPk(int n, int m, int p, int pk) {
        if (m > n) return 0;
        int num = factorialMod(n, p, pk);
        int den1 = factorialMod(m, p, pk);
        int den2 = factorialMod(n - m, p, pk);
        int den = (den1 * den2) % pk;
        int invDen = modInverse(den, pk); // 逆元
        int powP = countP(n, p) - countP(m, p) - countP(n - m, p);
        return (num * invDen % pk * powMod(p, powP, pk)) % pk;
    }

    // 计算模逆元
    public static int modInverse(int a, int m) {
        return powMod(a, m - 2, m);
    }

    // 中国剩余定理（CRT）合并同余方程
    public static int crt(List<Integer> remainders, List<Integer> mods) {
        int M = 1;
        for (int mod : mods) {
            M *= mod;
        }
        int res = 0;
        for (int i = 0; i < remainders.size(); i++) {
            int mi = mods.get(i);
            int Mi = M / mi;
            int invMi = modInverse(Mi, mi);
            res = (res + remainders.get(i) * Mi % M * invMi % M) % M;
        }
        return res;
    }

    // 扩展卢卡斯定理：计算 C(n, m) mod p（p 非质数）
    public static int exLucas(int n, int m, int p) {
        Map<Integer, Integer> factors = factorize(p);
        List<Integer> remainders = new ArrayList<>();
        List<Integer> mods = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : factors.entrySet()) {
            int prime = entry.getKey();
            int exp = entry.getValue();
            int pk = (int) Math.pow(prime, exp);
            int rem = combModPk(n, m, prime, pk);
            remainders.add(rem);
            mods.add(pk);
        }
        return crt(remainders, mods);
    }

    public static void main(String[] args) {
        int n = 100;
        int m = 50;
        int p = 12; // 非质数模数
        int result = exLucas(n, m, p);
        System.out.println("C(" + n + ", " + m + ") mod " + p + " = " + result);
    }
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.*;
public class Main{
  static int[]father;
  static long[]value;
  public static void main(String[] args){
    Scanner scan=new Scanner(System.in);
    int N=scan.nextInt();
    int M=scan.nextInt();
    int Q=scan.nextInt();
    father=new int[N+1];
    value=new long[N+1];
    init(N);
    for(int i=0;i<M;i++){
      int left=scan.nextInt();
      int right=scan.nextInt();
      long s=scan.nextLong();
      left--;
      union(left,right,s);
    }
    for(int i=0;i<Q;i++){
      int l=scan.nextInt();
      int r=scan.nextInt();
      l--;
      int lFa=find(l);
      int rFa=find(r);
      if(lFa==rFa){
        System.out.println(value[l]-value[r]);
      }else{
        System.out.println("UNKNOWN");
      }
    }
    scan.close();
  }
  static void init(int N){
    for(int i=0;i<=N;i++){
      father[i]=i;
    }
  }
  static int find(int x){
    if(x!=father[x]){
      int tmp=father[x];
      father[x]=find(father[x]);
      value[x]+=value[tmp];
    }
    return father[x];
  }
  static void union(int left,int right,long s){
    int lF=find(left);
    int rF=find(right);
    if(lF!=rF){
      int min=Math.min(lF,rF);
      int max=Math.max(lF,rF);
      father[min]=max;
      value[min]=Math.abs(value[right]-value[left]+s);
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
  static int N=110;
  static int n,Q;
  static long[][]cnt;
  static long[][]ans;
  static long[][]lns;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n=scan.nextInt();
        Q=scan.nextInt();
        cnt=new long[N][N];
        ans=new long[N][N];
        lns=new long[N][N];
        for(int i=1;i<=n;i++){
          for(int j=1;j<=n;j++){
            ans[i][j]=scan.nextLong();
          }
        }
        for(int i=1;i<=n;i++){
          for(int j=1;j<=n;j++){
            lns[i][j]=scan.nextInt();
            cnt[i][j]=lns[i][j];
          }
        }
        if(floyd()>Q){
          System.out.println(-1);
          return;
        }
        long l=0,r=10000010;
        while(l<r){
          long mid=l+r>>1;
          if(check(mid))r=mid;//minhua
          else l=mid+1;
        }
        System.out.println(r);
        scan.close();
    }
    static long floyd(){
      //最短路下线
      long a=0;
      for(int k=1;k<=n;k++){
          for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
              cnt[i][j]=Math.min(cnt[i][j],cnt[i][k]+cnt[k][j]);
            }
          }
        }
        for(int i=1;i<=n;i++){
          for(int j=1;j<=n;j++){
            a+=cnt[i][j];
          }
        }
        return a;
    }
    static boolean check(long x){
      for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
          cnt[i][j]=ans[i][j];
        }
      }
      long h=x/n;
      long s=x%n;
      for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
          if(i==j)continue;
          if(i<=s)cnt[i][j]=Math.max(lns[i][j],cnt[i][j]-1-h);
          else cnt[i][j]=Math.max(lns[i][j],cnt[i][j]-h);
          cnt[j][i]=cnt[i][j];
        }
      }
      return floyd()<=Q;
    }
}

dij

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package lanqiao;
import java.util.*;
public class dj {
    static int m,n;
    static long[][]dis;
    static boolean[][]st;
    static ArrayList<long[]>[][]list;
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        n=scan.nextInt();
        m=scan.nextInt();
        dis=new long[n+1][m+1];
        st=new boolean[n+1][m+1];
        int[][]a=new int[n+1][m+1];
        list=new ArrayList[n+1][m+1];
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                list[i][j]=new ArrayList<long[]>();
                a[i][j]=scan.nextInt();
            }
        }
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
            if(i>1)list[i][j].add(new long[] {i-1,j,a[i-1][j]});
            if(j>1)list[i][j].add(new long[] {i,j-1,a[i][j-1]});
            if(i<n)list[i][j].add(new long[] {i+1,j,a[i+1][j]});
            if(j<m)list[i][j].add(new long[] {i,j+1,a[i][j+1]});
            }
        }
        dij(a[1][1]);
        long max=0;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                max=Math.max(dis[i][j],max);
            }
        }
        System.out.println(max);
        scan.close();
    }
    static void dij(int start) {
        for(int i=1;i<=n;i++) {
            Arrays.fill(dis[i],Long.MAX_VALUE);
        }

        PriorityQueue<long[]>p=new PriorityQueue<long[]>(Comparator.comparing(k->k[2]));
        dis[1][1]=start;
        p.add(new long[]{1,1,start});
        while(!p.isEmpty()) {
            long[]t=p.poll();
            int x=(int)t[0];
            int y=(int)t[1];
            if(st[x][y])continue;
            st[x][y]=true;
            for(long[]a:list[x][y]) {
                int x1=(int)a[0];
                int y1=(int)a[1];
                long w=a[2];
                if(dis[x1][y1]>dis[x][y]+w) {
                    dis[x1][y1]=dis[x][y]+w;
                    p.add(new long[] {x1,y1,dis[x1][y1]});
                }
            }
        }

    }

}

dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
  static int N=110;
  static int n,Q;
  static long[][]cnt;
  static long[][]ans;
  static long[][]lns;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n=scan.nextInt();
        Q=scan.nextInt();
        cnt=new long[N][N];
        ans=new long[N][N];
        lns=new long[N][N];
        for(int i=1;i<=n;i++){
          for(int j=1;j<=n;j++){
            ans[i][j]=scan.nextLong();
          }
        }
        for(int i=1;i<=n;i++){
          for(int j=1;j<=n;j++){
            lns[i][j]=scan.nextInt();
            cnt[i][j]=lns[i][j];
          }
        }
        if(floyd()>Q){
          System.out.println(-1);
          return;
        }
        long l=0,r=10000010;
        while(l<r){
          long mid=l+r>>1;
          if(check(mid))r=mid;//minhua
          else l=mid+1;
        }
        System.out.println(r);
        scan.close();
    }
    static long floyd(){
      //最短路下线
      long a=0;
      for(int k=1;k<=n;k++){
          for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
              cnt[i][j]=Math.min(cnt[i][j],cnt[i][k]+cnt[k][j]);
            }
          }
        }
        for(int i=1;i<=n;i++){
          for(int j=1;j<=n;j++){
            a+=cnt[i][j];
          }
        }
        return a;
    }
    static boolean check(long x){
      for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
          cnt[i][j]=ans[i][j];
        }
      }
      long h=x/n;
      long s=x%n;
      for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
          if(i==j)continue;
          if(i<=s)cnt[i][j]=Math.max(lns[i][j],cnt[i][j]-1-h);
          else cnt[i][j]=Math.max(lns[i][j],cnt[i][j]-h);
          cnt[j][i]=cnt[i][j];
        }
      }
      return floyd()<=Q;
    }
}