算法-数论

目录

1 快速幂+模幂

欧拉定理：

同余 ≡

2 因子和

3 数组分割

1 快速幂+模幂

思路：

• 题目要求X=(ABC)2的n次方 mod （1e9+7）
• 规律：an*bn*cn=(bn-1*cn-1*an-1*cn-1*an-1*bn-1)=(an-1*bn-1*cn-1)2

=((an-2*bn-2*cn-2)2）2=((a1*b1*c1)2)的n次方

欧拉定理：

题中: ABC的1e9+6次方mod(1e9+6)与1mod(1e9+6)相等，为1

同余 ≡

import java.util.Scanner;

public class six {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t = scanner.nextInt();
        long mod= (long) 1e9+7;
        for (int i = 0; i < t; i++) {
            long a = scanner.nextLong();
            long b = scanner.nextLong();
            long c = scanner.nextLong();
            long n = scanner.nextLong();
            // 求abc的2的n次方幂
            // n<=1e9+7，2的n次方幂太大，使用欧拉定理转化
            long r = quickMi(2,n,mod-1);
            // 求ABC的2的r次方
//          会超出范围  long initial_number=((a%mod)*(b%mod)*(c%mod))%mod;
            // long最大范围小于10的19次方，abc最大均为10的9
            long initial_number=((a % mod) * (b % mod) % mod * (c % mod)) % mod;
            long result = quickMi(initial_number, r,mod)%mod;
            System.out.println(result);
        }
    }

    private static long quickMi(long dishu, long mi,long mod) {
        if (mi == 0) {
            return 1; // 任何数的0次方都是1
        }
        if (mi==1){
            return dishu%mod;
        }
        if (mi%2==0){
            // 偶数幂
            long num=quickMi(dishu,mi/2,mod);
            return (num*num)%mod;
        }else{
            // 奇数幂
            long num=quickMi(dishu,mi/2,mod);
            return (num * num  % mod * dishu) % mod;
        }
    }
    }
}

2 因子和

思路：

• 数x*f(x)是一个偶数，则该数是一个好数
• 题中数据量最大为1e7,时间复杂度为线性情况下才可以AC，那么想通过枚举一个数的所有因子，来计算因子和的方式显然是不可能的
• 采用数学方法

• • 如果一个数为偶数，那么它×一个数依然是偶数，所以偶数就是好数
  • 如果一个数为奇数

• • • 一个数的两个因子相乘=一个数，该数为奇数，而只有奇数*奇数仍然为奇数，想让因子和为偶数，那么必须有偶数个奇数因子，而本题中因子是小于x的，即x的因子在原来偶数对的情况下少了一个，有奇数个因子，那么想要让因子和为偶数，就必须在少一个因子，而类似9，25这样的平方根数，它的因子会出现相同的数，此时刚好少了一个因子，那么当该数为奇数并且为平方根数时，该数为好数

细节：

• 对一个数取平方根时，不采用Math.pow(number,0.5)的方式，因为返回的是double类型
• 使用Math.sqrt(number)，针对平方根优化，直接硬件级计算，精度更高

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;


public class Two {
    public static void main(String[] args) throws IOException {
        StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken();
        int t = (int)st.nval;
        for (int k = 0; k < t; k++) {
            // 数组长度
            st.nextToken();
            int n = (int)st.nval;
            // 提问次数
            st.nextToken();
            int q = (int)st.nval;
            long[]array=new long[n+1];
            for (int i = 1; i <= n; i++) {
                st.nextToken();
                array[i]=(long)st.nval;
            }
            long[]prefix=new long[n+1];
            boolean[]isHao=new boolean[n+1];
            for (int i = 1; i <= n; i++) {
                long number=array[i];
                boolean result;
                if (number%2==0){
                    result=true;
                } else if (Math.pow((long)Math.sqrt(number),2)==number) {
                    result= true;
                }else{
                    result=false;
                }
                isHao[i]=result;
                if (result){
                    prefix[i]=prefix[i-1]+1;
                } else{
                    prefix[i]=prefix[i-1];
                }
            }
            for (int i = 0; i < q; i++) {
                st.nextToken();
                int l = (int)st.nval;
                st.nextToken();
                int r = (int)st.nval;
                if (isHao[l]){
                    System.out.println(prefix[r]-prefix[l]+1);
                }else{
                    System.out.println(prefix[r]-prefix[l]);
                }
            }
        }

    }


}

3 数组分割

暴力搜索思路：

• 深度搜索枚举出A的所有子集，记为R1，未在R1中的元素即为R2
• 该算法的时间复杂度为O(2n),可以通过20%的测试

package LanQiaoBei;

import java.util.Scanner;

public class P14_two {
        static long count=0L;
        public static void main(String[] args) {
            Scanner scanner=new Scanner(System.in);
            int t=scanner.nextInt();
            for (int i = 0; i < t; i++) {
                int n=scanner.nextInt();
                long[]number=new long[n];
                long sum=0;
                for (int j = 0; j < n; j++) {
                    number[j]=scanner.nextLong();
                    sum+=number[j];
                }
                count=0;
                dfs(number,0,0,sum);
                count=(long) (count%(10e9+7));
                System.out.println(count);
            }
        }
        public static void dfs(long[]number,int start,long r,long sum) {
            if (r%2==0 && (sum-r)%2==0 ) {
                count++;
            }
            for (int i = start; i < number.length; i++) {
                dfs(number, i+1,r+number[i],sum);
            }
        }
    }

数学规律思路

• 根据奇偶数的个数，判断子集可以为偶数的个数
• 将一个数组分成两份，然后两份都是偶数
• 如果有奇数个奇数，那么一定会有R1或R2和是奇数，比如有1个奇数，那么这个奇数放到哪个数组哪个数组和就是奇数，因为奇数+奇数为偶数，没有与它配对的
• 如果奇数为偶数

• • 0个奇数，那么无论怎么选择，两个数组和都是偶数，每个数有2种选择，N个数，有2n个不同的情况
  • 奇数为偶数，那么奇数必须配对存在，偶数个奇数形成一个偶数，当总和为偶数且存在奇数时，子集和为偶数的数目恒为2的n-1次方
  • 例如 1,3 形成2个偶数子集，{1,3}和{ }空集
  • 1，3，5，7 {1,3}，{1,5}，{1,7}，{3,5}，{3,7}，{5,7}，{1,3,5,7}，{ }形成8个偶数和子集

import java.text.DateFormatSymbols;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner scanner=new Scanner(System.in);
    int t=scanner.nextInt();
    long mod=(long) (1e9+7);
    for (int i = 0; i < t; i++) {
      int n=scanner.nextInt();
      long[]number=new long[n];
      long sum=0;
      int evenNumber=0;
      int oddNumber=0;
      for (int j = 0; j < n; j++) {
        number[j]=scanner.nextLong();
        if ((number[j]&1)==0) {
          // 偶数
          evenNumber++;
        }else {
          oddNumber++;
        }
      }
      if ((oddNumber&1)!=0) {
        // 奇数
        System.out.println(0);
      }else {
        if (oddNumber==0) {
          sum=(int)(Math.pow(2,n)%mod);
          System.out.println(sum);
        }else {
          sum=(int)(Math.pow(2,n-1)%mod);
          System.out.println(sum);
        }
      }
    }
  }
}