北向眼


私信TA

用户名:uq_91541132464

访问量:2098

签 名:

题解都是为了做笔记,备战中

等  级
排  名 1821
经  验 2478
参赛次数 1
文章发表 15
年  龄 20
在职情况 学生
学  校 江西财经大学
专  业 软件工程

  自我简介:

题解都是为了做笔记,备战中 //更新,javaB国一已拿,转战Acwing

TA的其他文章

第一种方法:


遍历1到sqrt(num),如果num能被循环的i整除,则当前数为num的约数,其背面num/i也为num的约数

当num为一个平方数时,i会计入两次,所以添加一个a/i!=i来判段

import java.util.HashSet;
import java.util.Set;

public class Main{
	static Set set=new HashSet<>();
	public static void main(String[] args) {
	//这里举例求2000的约数
		int a=2000;
		//遍历1到sqrt(2000)
		for(int i=1;i*i<=a;i++) {
			if(a%i==0) {
			//加入集合
				set.add(i);
				//判段是否为i*i=num,排掉重复
				if(a/i!=i) {
					set.add(a/i);
				}
			}
		}
		//输出约数
		for(int i:set) {
			System.out.println(i);
		}
		System.out.println();
		//输出约数个数
		System.out.println(set.size());
	}
	
}

第二种方法:

其实第二种方法我用的还比较多,从蓝桥杯20年国赛第三题用的就是这种方法好算一些,但是这个方法好像在这道题时间会溢出,麻了。

    第一步:欧拉筛选质数

    第二部:判段传入num是否为质数,如果为质数,则直接返回2,如果不是则遍历2到num-1,把num的所有质数个数找出来,比如20可以分成2个2和一个5;选2有3种情况,选一个2\两个2或者不选,5也可以分为0或者1,组合出来的结果就是(2+1)*(1+1)=6。此题也是如此,找到一个数的所有质数个数,把每个质数个数+1全部乘起来就是ans。

    第三部,遍历a到b,找出div返回值最大的;

import java.io.*;
public class Main{
	static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	static boolean[] isPrime;
	static int a,b;
	public static void main(String[] args) throws IOException {
		String[] temp=bf.readLine().split(" ");
		int a=Integer.parseInt(temp[0]);
		int b=Integer.parseInt(temp[1]);
		//欧拉筛
		isPrime=new boolean[b+1];
		isPrime[0]=isPrime[1]=true;
		for(int i=2;i*i<=b;i++) {
			if(!isPrime[i]) {
				for(int j=2*i;j<=b;j+=i) {
					isPrime[j]=true;
				}
			}
		}
		long max=0;
		for(int i=a;i<=b;i++){
		   max=Math.max(max,div(i));
		}
		pw.print(max);
		pw.flush();
	}
	public static long div(int num) {
		long ans=1;
		int[] arr=new int[num];
		//判段是否为质数
		if(!isPrime[num]) {
			return 2;
		}else {
		//存储当前变量,避免被下面运算修改
			int temp=num;
			//循环2至num-1,如果为质数就arr[i]++
			for(int i=2;i<num;i++) {
				if(!isPrime[i]) {
					while(temp%i==0) {
						temp/=i;
						arr[i]++;
					}
				}
			}
			//组合
			for(int i=1;i<num;i++) {
				if(arr[i]!=0) {
					ans*=(arr[i]+1);
				}
			}
		}
		return ans;
	}
}

第三种方法:

这个其实是很容易的方法,但也是过这题的方法。

有点像欧拉筛,也是一个很好的方法,遍历1到b,把它的倍数存到相应的数组中去,这样就可以得到每个数的约数了。循环a-b,获得最大数

import java.io.*;
public class Main{
	static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	public static void main(String[] args) throws IOException {
	//读取
		String[] temp=bf.readLine().split(" ");
		int a=Integer.parseInt(temp[0]);
		int b=Integer.parseInt(temp[1]);
		int[] arr=new int[b+1];
		//遍历1到b,把他的倍数++
		for(int i=1;i<=b;i++) {
			for(int j=i;j<=b;j+=i) {
				arr[j]++;
			}
		}
		int max=0;
		for(int i=a;i<=b;i++) {
			max=Math.max(arr[i],max);
		}
		pw.print(max);
		pw.flush();
	}
}


 

0.0分

2 人评分

  评论区