头像

机械佬也想学编程




离线:1小时前


活动打卡代码 AcWing 872. 最大公约数

欧几里得算法,也叫辗转相除法

定理:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数

import java.util.*;

public class Main{

    public static void main(String[] args){

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n > 0 ){
            n --;
            int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(gcd(a, b));
        }
    }

    private static int gcd(int a, int b){
        return b > 0 ? gcd(b, a % b) : a; 
    }

}


活动打卡代码 AcWing 871. 约数之和

约数之和公式:
$$
f(n) = (p^0_1 + p^1_1 + p^2_1 + … + p^{\alpha_1}_1)(p^0_2 + p^1_2 + p^2_2 + … + p^{\alpha_2}_2)\cdot\cdot\cdot(p^0_k + p^1_k + p^2_k + … + p^{\alpha_k}_k)
$$

解释:每个括号里面就是每一个质数的任一个次幂(次幂范围 [0,$\alpha_i$])之和,如果把括号拆开,就是每个括号里面选一个数乘起来,再把所有选择加起来。每个括号选一个数乘起来,不正对应每一个约数的值吗?所以约数和就是上面这个式子。

import java.util.*;

public class Main{

    private static TreeMap<Integer, Integer> primes = new TreeMap<>();
    private static long mod = (long)1e9 + 7;

    public static void main(String[] args){

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n > 0){
            n--;
            int a = in.nextInt();
            divide(a);
        }

        long res = 1;

        for (Map.Entry<Integer, Integer> entry : primes.entrySet()){
            int base = entry.getKey();
            int exp = entry.getValue();
            long t = 1;
            while (exp > 0){
                t = (t * base + 1) % mod;
                exp --;
            }
            res = res * t % mod;
        }
        System.out.println(res);
    }

    private static void divide(int n){

        for (int i = 2; i <= n / i; i++){
            while (n % i == 0){
                n /= i;
                primes.put(i, primes.getOrDefault(i, 0) + 1);
            }
        }

        if (n > 1){
            primes.put(n, primes.getOrDefault(n, 0) + 1);
        }
    }

}



活动打卡代码 AcWing 870. 约数个数

约数个数定理:对于一个正整数n,可以分解质因数为:

$$
n = p_1 ^{\alpha_1} \cdot p_2 ^{\alpha_2} \cdot p_3 ^{\alpha_3} \cdot \cdot \cdot p_k ^{\alpha_1}
$$
由约数的定义,得约数个数为:
$$
(\alpha_1+1)(\alpha_2+1)(\alpha_3+1)\cdot\cdot\cdot (\alpha_k+1)
$$

public class Main{

    private static TreeMap<Integer, Integer> primes = new TreeMap<>();
    private static long mod = (long) (1e9 + 7);

    public static void main(String[] args){

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n > 0){
            n --;
            int a = in.nextInt();
            divide(a);
        }

        long res = 1;
        for (int val : primes.values()){
            res = res * (val + 1) % mod;
        }
        System.out.println(res % mod);
    }

    private static void divide(int n){

        for(int i = 2; i <= n / i; i ++){
            while (n % i == 0){
                n /= i;
                primes.put(i, primes.getOrDefault(i, 0) + 1);
            }
        }
        if (n > 1){
            primes.put(n, primes.getOrDefault(n, 0) + 1);
        }
    }
}



活动打卡代码 AcWing 869. 试除法求约数

import java.util.*;

public class Main{


    private static List<Integer> divisors(int n){

        List<Integer> res = new ArrayList<>();

        for (int i = 1; i <= n / i; i++){
            if (n % i == 0){
                res.add(i);
                if (n / i != i){
                    res.add(n/i);
                }
            }
        }
        Collections.sort(res);
        return res;

    }


    public static void main(String[] args){

        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        while (n > 0){
            n --;
            int a = in.nextInt();
            List<Integer> res = divisors(a);
            for (int i : res){
                System.out.print(i + " ");
            }
            System.out.println();
        }

    }

}



活动打卡代码 AcWing 868. 筛质数

筛质数

给定一个正整数n,请你求出1~n中质数的个数

朴素做法,从头到尾遍历所有的数,并筛掉它后面的倍数,时间复杂度$n/2 + n/3 + … +n/n$ = O($nlogn$)

private static int[] primes;
private static boolean[] st;
private static int cnt;

private static void getPrimes(int n){
    cnt = 0;
    st = new boolean[n+10];
    primes = new int[n+10];
    for (int i = 2; i <= n; i++){
        if (!st[i]){
            primes[cnt ++] = i;
        }
        // 不管i是质数还是合数,都筛掉其倍数
        for (int j = i; j <= n; j += i){
            st[j] = true;
        }
    }
}

改进:埃氏筛法,只需要筛掉质数的倍数即可

根据质数定理:1~n中有$n / logn$个质数,求得时间复杂度为O($nlog(logn)$)

private static int[] primes;
private static boolean[] st;
private static int cnt;

private static void getPrimes(int n){
    cnt = 0;
    st = new boolean[n+10];
    primes = new int[n+10];
    for (int i = 2; i <= n; i++){
        if (!st[i]){
            primes[cnt++] = i;
            // 只筛掉质数的倍数
            for(int j = i; j <= n; j+=i){
                st[j] = true;
            }
        }
    }
}

线性筛法:把每一个合数用它的最小质因子筛掉

private static int[] primes;
private static boolean[] st;
private static int cnt;

private static void getPrimes(int n){
    cnt = 0;
    st = new boolean[n+10];
    primes = new int[n+10];
    for (int i = 2; i <= n; i++){
        if (!st[i]){
            primes[cnt++] = i;
        }
        for (int j = 0; primes[j] <= n / i; j++){
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}


活动打卡代码 AcWing 867. 分解质因数

分解质因数要从最小的质数2开始除,直到没有因素2再除以下一个质数3,直至除得的商也为质数。

先来暴力做法,枚举所有的质因数,O(n):

public static void divide(int n){
    for (int i = 2; i < n; i ++){
        if (n % 2 == 0){
            int count = 0; // 记录质因数i出现的次数
            while (n % i == 0){
                n /= i;
                count ++;
            }
            System.out.println(i + " " + count);
        }
    }
}

这里有个细节,对一个数分解质因数应该枚举这个数的所有质因数,但第2行枚举了所有的数,是不是错了?其实没有错,因为枚举到i的时候,已经把2 ~ i-1所有n的质因子已经除干净了,如果又有n % i == 0成立的话,n是i的倍数,i当中也不包含任何2 ~ i-1的质因子,所以i一定是质数。

对上述暴力做法改进,由于一个正整数n最多只有一个质因数大于$\sqrt n$,容易只需要枚举小于$\sqrt n$的质因数,对于最后一个大于$\sqrt n$的质因数单独处理。时间复杂度O($\sqrt n$)

public static void divide(int n){
    for (int i = 2; i <= n / i; i++){
        if (n % i == 0){
            int count = 0;
            while (n % i == 0){
                n /= i;
                count++;
            }
            System.out.println(i + " " + count);
        }
    }
    if (n > 1){
        System.out.println(n + " " +1);
    }
    System.out.println();
}



import java.util.*;

public class Main{

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for(int i = 0; i < n; i++){
            int a = in.nextInt();
            if (isPrime(a)){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }
    }

    public static boolean isPrime(int n){
        if(n < 2){
            return false;
        }
        for(int i = 2; i <= n / i; i ++){
            if (n % i == 0){
                return false;
            }
        }
        return true;
    }

}




/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode quickSortList(ListNode head) {

        if (head == null || head.next == null){
            return head;
        }

        // 声明左、中、右三个链表
        ListNode left = new ListNode(-1);
        ListNode right = new ListNode(-1);
        ListNode mid = new ListNode(-1);
        //快排每次选择第一个节点的值作为对比
        int v = head.val;
        while (head != null){
            ListNode temp = head.next;
            //将小于v的值加入到left链表中
            if (head.val < v){
                head.next = left.next;
                left.next = head;
            //将大于v的值加入到right链表中
            }else if (head.val > v){
                head.next = right.next;
                right.next = head;
            //将等于v的值加入到mid链表中
            }else{
                head.next = mid.next;
                mid.next = head;
            }
            head = temp;
        }
        //递归排序做链表和右链表
        left.next = quickSortList(left.next);
        right.next = quickSortList(right.next);
        //找到左链表的尾节点,令其指向中链表
        ListNode t = left;
        while (t.next != null){
            t = t.next;
        }
        t.next = mid.next;
        //再找到中链表的尾节点,令其指向右链表
        while (t.next != null){
            t = t.next;
        }
        t.next = right.next;
        return left.next;
    }
}


活动打卡代码 AcWing 905. 区间选点


n = int(input())
a = []
for _ in range(n):
    t = list(map(int, input().split()))
    a.append(t)


a.sort(key = lambda x:x[1])
res = 0
last = -1e10
for l, r in a:
    if l > last:
        res += 1
        last = r
print(res)

import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] a = new int[n][2];

        for(int i = 0; i < n; i++){
            a[i][0] = in.nextInt();
            a[i][1] = in.nextInt();
        }

        Arrays.sort(a, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                if (o1[1] == o2[1]) return o1[0] - o2[0];
                return o1[1] - o2[1];
            }
        });

        int res = 0;
        double last = - 1e9;
        for (int i = 0; i < n; i++){
            if (a[i][0] > last){
                res ++;
                last = a[i][1];
            }
        }
        System.out.print(res);
    }
}



n = int(input())
state1 = []
state2 = []
state3 = 1
cnt = 20
def dfs():
    global cnt, state3
    if cnt == 0:
        return
    if len(state1) == n:
        for num in state1:
            print(num, end="")
        print()
        cnt -= 1

    if state2:      # 为了保证字典序,先让栈里的火车出来,再添加新的火车进去
        state1.append(state2.pop())
        dfs()
        state2.append(state1.pop())
    if state3 <= n:
        state2.append(state3)
        state3 += 1
        dfs()
        state3 -= 1
        state2.pop()
dfs()