阅读 15

基础数论知识一些总结

快速幂

在这里插入图片描述
非递归版

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		for(int i=0;i<t;i++)
		{
			long b=sc.nextLong();
			long c=1000000007;long a=2;
			long res = 1;
	        a %= c;
	        for (; b != 0; b /= 2) {
	            if (b % 2 == 1)
	                res = (res * a) % c;
	            a = (a * a) % c;
	        }
			System.out.println(res);		
		}
	}
}
复制代码

递归版(用的比较多)

import java.util.Scanner;
public class Main {
   static long c=1000000007;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t=sc.nextInt();
		for(int i=0;i<t;i++)
		{
			long a=2;
			long b=sc.nextLong();			
			long value=divide((long)2,b);
			System.out.println(value%c);
		}
	}
	private static long divide(long a,long b) {
		if(b==0)return 1;
		else if(b%2==0) {return divide((a%c)*(a%c),b/2)%c;}
		else return a%c*divide((a%c)*(a%c),(b-1)/2)%c;
	}
}
复制代码

矩阵快速幂

题目链接 核心思想为:

在这里插入图片描述
从右往左。可以一直递推,然后到最后一项,然后快速幂求矩阵,矩阵最终的结果就是所求结果。 更新java的矩阵通用乘法可以表示为,可以将下列代码替换道ac代码中:

static int [][] multiplication(int a[][],int b[][]){//
	  int x=a.length;//a[0].length=b.length 为满足条件
	  int y=b[0].length;//确定每一排有几个
	  int c[][]=new int [2][2];
	  for(int i=0;i<x;i++)
		  for(int j=0;j<y;j++)
		  {
			  //需要确定每一个元素
			  //c[i][j];
			  for(int t=0;t<b.length;t++)
			  {
				  c[i][j]+=(a[i][t]%10000)*(b[t][j]%10000);
				  c[i][j]%=10000;
			  }
		  }
	  
	   return c;  
  }
复制代码
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		Scanner sc=new Scanner(System.in);		
		while(sc.hasNext())
		{
		int n=sc.nextInt();
		if(n==-1)break;
		if(n==0) {System.out.println(0);}
		else {
		n-=1;//
		int a[][]= {{1,1},{1,0}};
		int b[][]={{1,0},{0,1}};//单位矩阵
	    int time=0;
		while(n>0)
		{
		    if(n%2==1)
			{
		    	b=q(a, b);
			}	
		    a=q(a, a);n/=2;
		}
		
		System.out.println((b[0][0]));
		}
		}
	}
static int [][] q(int a[][],int b[][]){//
	  int value1=a[0][0]*b[0][0]%10000+a[0][1]*b[1][0]%10000;//左上
	  int value2=a[0][0]*b[0][1]%10000+a[0][1]*b[1][1]%10000;//左上
	  int value3=a[1][0]*b[0][0]%10000+a[1][1]*b[1][0]%10000;//左上
	  int value4=a[1][0]*b[0][1]%10000+a[1][1]*b[1][1]%10000;//左上
	  int c[][]=new int [2][2];
	  c[0][0]=value1%10000;
	  c[0][1]=value2%10000;
	  c[1][0]=value3%10000;
	  c[1][1]=value4%10000;
	   return c;  
  }
}
复制代码

拓展欧几里得

拓展欧几里得模板 参考:哈尔滨理工大学ACM培训资料汇编/ACM-ICPC培训资料汇编* 基本原理 :设 a 和 b 不全为 0,==则存在整数 x,y 使得 xa+yb=gcd(a,b)=c== 对于辗转相除法的最后一项 此时 b=0,则 gcd(a,b)=1a+0b,(这个a,b是经过gcd的最后一项a,b)

因为gcd(a,b)=gcd(b,a%b)

则有x *a+y *b=x1 *b+y1 * (a%b) 将等式右边变形,

b *x1+(a%b) *y1=b *x1+(a-(a/b) *b) *y1=a *y1+b *(x1-(a/b) *y1)

则,x=y1,y=x1-(a/b) *y1 则可由后向前迭代得到 x,y

解题思路 :

对于扩展欧几里德定理的题,一般都需要进行一定的推导之后得到一个形式为 xa+yb=c 的方程,然后根据 c 确定解是否存在, 如果 c 可以被 gcd(a,b)整除,那么方程有 解,否则方程无解。 而且所得的解是不唯一的,对于一组解 x0,y0 则其所有解可以表示为 x=x0+b/gcd(a,b)*t,y=y0-a/gcd(a,b)*t,t=0,+1,+2……一般会要求找出 x 或者 y 的最小正整数 解,这个时候需要做一些调整。

总的来说。递归是一来一回的过程,在gcd中,我们只用到了去的过程,求的最大公约数,而在exgcd中,我们发现了在来的过程中,某些数按照一定的规则变化,可以得到我们想要的结果而已。

static long x=0,y=0;
...
static long extgcd(long a,long b)
	{
		if(b==0) {x=1;y=0;return a;}
		long ans=extgcd(b, a%b);
		long team=x;
		x=y;
		y=team-a/b*y;
		return ans;
	}
复制代码

求逆元: 从拓展欧几里得中知道可以求ax+by=c,一般是解决这类问题

当a,b互质时候。c一定等于1.因为gcd(a,b)=1,c必须被gcd整除,那么如果有解一定是1.

那么ax+by=1.

求逆元一般形式(求a关于1mod m的逆元)

ax≡1 (mod m). x就是所求的逆元

变形为 ax+bm=1

这样就可以运用拓展欧几里得(但是x要大于0处理)

  static long x=0;static long y=0;//全局变量
  ......
   long q=tgcd(a,b);
           // long x1=x;
   if(1%q!=0) {out.println("Not Exist");}
   else {
       while(x<=0){//x*a+y*b=1  要求x>0这样并且要求x最小,那么这样操作就相当于+ab-ab操作。刚开始还没明白
             x+=b;
             y-=a;
         }
    system.out.println(x);}//

 static long tgcd(long a,long b)
    {
        if(b==0) {x=1;y=0;return a;}
        long ans=tgcd(b,a%b);
        long team=x;
        x=y;
        y=team-a/b*y;
       // System.out.println(x);
        return ans;

    }
复制代码

还有用小费马可以求逆元,就不介绍了。

例题

杭电2669 给a,b求Xa + Yb = 1.如果没有则输出sorry。 可以通过拓展欧几里得指导Xa + Yb = gcd(a,b). 不言而喻要判断gcd(a,b)是否等于1.如果不等于1,那么就是sorry。如果等于一,那么还不能让x小于0,要对x,y进行加减操作满足x>0;拓展欧几里得是通过递归从下往上进行运算。

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

/*
 * 拓展欧几里得
 */
public class hdu2669 {
      static long x=0;static long y=0;
	public static void main(String[] args) throws IOException {
		// TODO 自动生成的方法存根
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while(in.nextToken()!=StreamTokenizer.TT_EOF)
		{
			long a=(long)in.nval;
			in.nextToken();
			long b=(long)in.nval;
			long q=tgcd(a,b);
			if(1%q!=0) {out.println("sorry");}//gcd要和要求相等(这里等于1)
			else {
				while(x<=0){//x*a+y*b=1  要求x>0这样并且要求x最小,那么这样操作就相当于+ab-ab操作。刚开始还没明白
					x+=b;
					y-=a;
				}
				out.println(x+" "+y);}//
			out.flush();
		}		
	}
	static long tgcd(long a,long b)
	{
		if(b==0) {x=1;y=0;return a;}
		long ans=tgcd(b,a%b);
		long team=x;
		x=y;
		y=team-a/b*y;
		return ans;
		
	}
}
复制代码

题目:

两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。

我们把这两只青蛙分别叫做==青蛙A和青蛙B==,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。 Input

输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。 Output 输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible" Sample Input 1 2 3 4 5 Sample Output 4

分析

拓展欧几里得以前记过

分析一下设见面时间为t。青蛙A的位置是x+mt;青蛙B的位置是y+nt;两只青蛙项目,那么说明两只青蛙之间要么谁比谁多整数圈数。那么就得到x+mt-(y+nt)=k*L.变形一下(m-n)t-kL=(y-x).这就是m-n,L,y-x分别已知,而t和k未知,求最少的t.(t越少跳的越少。)

那么设m-n=a,L=b,t=X,-k=Y,y-x=c.原始就是aX+bY=c,其中a,b,c已知,求X最小正整数。你要判断c是否与gcd(a,b)互质,如果不互质则没有结果。

接着你求出的初始X是gcd(a,b)的情况,你要判断c是否是gcd的倍数,如果跟他互质,那么凉凉,不可能遇到,不满足extgcd的条件,如果是倍数。假设n倍,你可以你可以nXa,nYa,c相当于同时扩大倍的一种解,但是这不一定是最优解,你需要根据实际加减操作找到最小正解!

ac代码

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

public class poj1061 {

	static long X=0; static long Y=0;
	public static void main(String[] args) throws IOException {
		// TODO 自动生成的方法存根
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();long x=(long)in.nval;//A起始位置
		in.nextToken();long y=(long)in.nval;//B起始位置
		in.nextToken();long m=(long)in.nval;//A的速率
		in.nextToken();long n=(long)in.nval;//B的速率
		in.nextToken();long L=(long)in.nval;//长度

		long a=m-n;
		long c=y-x;
		long b=L;
		if(a<0) {a=-a;c=-c;}
		long res=extgcd(a,b);//  res=gcd(a,b)
		//c必须是res的倍数,如果互质的话就不满足拓展欧几里得的方程式,而对应的结果首先要跟着倍数扩大
		if(c%res!=0) {out.println("Impossible");}
		else {
			/*
			 * 可能难理解一点
			 * x=x0+(b/gcd(a,b))*t
			 * x=x0+(b/res)*t找到最小的正整数x,那么就是x%(b/res)了,如果小于0就是(x%b/res)+b/res了
			 */
			 X=X*(c/res);
            long t=b/res;
            if(X>=0)
                X=X%t;
            else
                X=X%t+t;
		    out.println(X);
		}
		out.flush();

	}
	private static long extgcd(long a, long b) {
		if(b==0)
		{
			X=1;Y=0;
			return a;
		}
		long res=extgcd(b, a%b);
		long team=X;
		X=Y;
		Y=team-(a/b)*Y;
		return res;
	}
}
复制代码

github地址

素数筛

在判定素数的问题中,随着不断学习,里面的拓展性也在不断地增加。

问题:判定一个数是否为素数:

想都不想的方法:

static boolean isprime(int value){
  for(int i=2;i<value;i++)
	{
	   if(value%i==0)
	   {return false;}
	}
	return true;
}
复制代码

暴力从开始判断的方法。复杂度O(n)。当数据大于1e7左右基本就爆了。更别说多组输入了

稍微思考数据组成

对于一个数n如果==不是素数==,一定有a*b=n(a<b);a<根号n,b>根号n,所以只要出现一定是成双成对。所以你只要==找到1个==就能说明这个数不是素数。所以从开始遍历到a是最省时的方法。因为a是log级。算法复杂度为O(logn)所以代码为:

static boolean isprime(int value)
{
  for(int i=2;i*i<value+1;i++)
	{
	   if(value%i==0)
	   {return false;}
	}
	return true;
}
复制代码

这种情况能够基本单输入的素数问题。但是遇到多个输入肯定也会GG的。

埃拉托斯特尼(Eratosthenes)筛法

问题:多个输入,问关于素数相关的问题。 如果用上述方法肯定爆。多组输入的最好解决办法是打表。至于打表,如果上述的打表nlogn打表的话会TLE,所以就要换一种思考方式。

埃氏筛的核心思想就是==将素数的倍数确定为合数==。对于一个从2开始连续数据,我们假设其中每一个都是素数。如果一个数为素数,那么这个数的倍数一定也是素数。所以算法大致流程: 2: [i=(2+2)—>(+2)数组尾],4,6,8,10 * * 不是素数 3: [i=(3+3)—>(+3)数组尾],6,9,12 * * 不是素数 4: [i=4]不是素数,跳过 5: . . . . . . . . . . . . 这个到除了前面几次的计算量多一点,到后面随着数据增大对整个复杂度相加是比较小的,算法复杂度为O(nloglogn);别小瞧多的这个logn,数据量大一个log可能少不少个0,那时间也是十倍百倍甚至更多的差距。 具体代码为

static boolean isprime[];
static long prime[];
static void getprime()
	{
		prime=new long[100001];//记录第几个prime
	    int index=0;
		isprime=new boolean [1000001];
		for(int i=2;i<1000001;i++)
		{
			if(!isprime[i])
			{
				prime[index++]=i;
			}
			for(int j=i+i;j<1000000;j=j+i)//他的所有倍数都over
			{
				isprime[j]=true;					
			}
		}
	}
复制代码

欧拉筛——线性筛

对于上述的埃氏筛,虽然能解决大部分的问题。但是不难发现里面还是有挺多不够精简的地方,比如有的地方会重复访问。而欧拉筛在埃氏筛的基础上进行优化,达到O(n)的复杂度。

static boolean isprime[];
static int prime[];
static void getprimeoula()// 欧拉筛
	{
		prime = new int[100001];// 记录第几个prime
		int index = 0;
		isprime = new boolean[1000001];
		for (int i = 2; i < 1000001; i++) {
			if (!isprime[i]) {
				prime[index++] = i;
			}
			for (int j = 0; j < index && i * prime[j] <= 100000; j++){
				isprime[i * prime[j]] = true;// 
				if (i % prime[j] == 0)
					break;
			}
		}

	}
复制代码

唯一分解定理

算数分解定理(唯一分解定理):

算数分解定理(唯一分解定理):

定义:

任何一个大于1的自然数 N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积 N=P1a1 P2a2P3a3…Pnan,这里P1<P2<P3…<Pn均为质数,其中指数ai是正整数。这样的分解称为 N 的标准分解式.

应用:对于一个正整数n,如果n=q1a1 * q2 a2 * …* qnan,那么他的正因数个数为(1+a1) * (1+a2)* . . . *(1+an);

样例:

1000=2* 500=2* (2 * 250)=2 * 2 *( 2 * 125)=2 * 2 * 2 *(5 * 25)=2 * 2 * 2 * 5 * (5 *5)=23*53.可以看的出来基本策略就是从2开始除,直到不是2的倍数然后网上递增求。

计算方法:

计算n的分解方式。主要是通过数的自身对从最小的质数开始整除除一直到不能整除,直到跳出限制条件。

  1. 你可以从2到n;逐个遍历判断,满足条件的话就在数组中添加对应的count。当然,每被计算一次的时候,这个数就要被除一次。

  2. 上面方法对于大的数据显然复杂度太高。其实你可以从2遍历到根号n+1(i * i<n+1)停止,因为最大的理想乘积是i*i=n,其他的数据都是一个左,一个右面。最终分解的时候如果都分到这步了说明要么后面不剩,要么就是剩一个大质数

  3. 上面虽然从数的量级减少了不少,但是会遍历很多没用的合数,比如遍历过2所有而的倍数都不需要遍历判断,所以我们只需要遍历素数。素数打表遍历素数,当遇到多组输入,数据要求较高的时候,先用素数筛打表,把素数预处理,然后直接从2-素数数组中遍历即可,因为如果一个数能被拆,那么他如果不能被拆,他就是素数,如果它还能被拆,那么它就是合数。所以一个数被分解到最后都是素数的次幂相乘!很重要!这样能够省的更多的时间。可以参考素数筛模板

核心代码:
不打表:

for(int j=2;j*j<n+1;j++)
{
		while(n%j==0)
		{
		     n/=j;
		      //根据需求操作
		}
		//根据需求操作...
	}
复制代码

打表:

static int index=0;//根据数据范围范围内素数的最后一个位置prime[index]
long prime[]=new long[100001];
boolean isprime[]=new boolean[1000001];
for(int i=2;i<1000001;i++)//埃拉托色尼筛选法
{
	if(!isprime[i])
	{
		prime[index++]=i;
		for(int j=i+i;j<1000000;j=j+i)
		{
			isprime[j]=true;					
		}
	}
}
........
........
    // int n;
	for(int j=0;j<index;j++)
	{
			if(n==0||prime[j]>n) {break;}//素数已经超出无法最大的数,退出
			long team=0;//其他操作,可以是你自己的逻辑
		    while(c%prime[j]==0)
		    {
		    	c/=prime[j];
		    	team++;//其他操作
		    }
		    number*=(1+team);//其他操作
		}	
复制代码

唯一分解定义有什么用?

例如给一个1000,这样的数,问有多少种可能组合使得a * b=1000.或者求a*b中在那个范围内a,b的排列次数。

首先要了解一个唯一分解定理的应用:对于一个正整数n,如果n=q1a1 * q2 a2 * …* qnan,那么他的正因数个数为(1+a1) * (1+a2)(1+an);对于这个,就可以衍生其他问题,比如找两个因数的组合情况,可能性,在那个范围等等。其实这就是一个组合问题。对于每一个数有t个,能够影响最终结果的就是这个素数出现的次数。如果细看虽然每个数的概率都是可能出现和不出现的1/2.但是对于最终结果就是:出现0次,出现1次,出现。。。,出现t次。所以这个数对结果出现的可能行变成了原来次数*(1+t).以此类推,便可得到所有的因数可能的结果。

就例如1000=23 * 53:
对于结果首先2和5是独立互不影响的。所以对于一个因数。质数2的搭配有四种,出现0个,1个,2个或3个。同理质数5的搭配也是4种,所以最终因数可能出现的次数是4 * 4=1*(3+1)*(3+1)=16个。

### 例题 看下[hdu5248](http://acm.hdu.edu.cn/showproblem.php?pid=5428)

题意:给出n个数,求这n个数中最小的两个因数乘积,题意有些小的歧义不太好理解。说明白了就是让你从n个数分解找最小的两个因子相乘.(1不满足因为1没有2个及以上因子).

思路:数据量不大,可以不打表直接素数分解。其实每个数找到2个因子就可以停止了,放到list或者数组中,最后排序判断因子是否大于等于2个。按照要求输出

附上ac代码:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class hdu5248 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		for(int q=0;q<T;q++)
		{
			int n=sc.nextInt();
			List<Long>list=new ArrayList<Long>();
			for(int i=0;i<n;i++)
			{
				long te=sc.nextLong();
				int num=0;
				for(int j=2;(long)j*j<te+1;j++)
				{
					while(te%j==0)
					{
						list.add((long) j);
						te/=j;
						num++;
					}
					if(num>2)break;//其实找到两个就不用找了
				}
				if(te>1) {list.add(te);}
			}
			if(list.size()<2)
				System.out.println(-1);
			else {
				list.sort(null);
				System.out.println((long)(list.get(0)*list.get(1)));
			}
		}

	}
}
复制代码

lightoj1341 题目大意:给个面积s。一个边b,问最小边大于b的所有可能情况。 思路:整体-多余。先求出所有的排列次数,然后除以二(要求组合队数)。再从0头到b开始剪掉多余的情况。不需要考虑特大的那边,因为是对称的已经除以过二了。 ac代码:

埃氏筛

import java.util.Scanner;
public class testC {
static int index=0;
public static void main(String[] args) {
	// TODO 自动生成的方法存根
	long prime[]=new long[100001];
	boolean isprime[]=new boolean[1000001];
	for(int i=2;i<1000001;i++)//埃拉托色尼筛选法
	{
		if(!isprime[i])
		{
			prime[index++]=i;
			for(int j=i+i;j<1000000;j=j+i)
			{
				isprime[j]=true;					
			}
		}
	}
	Scanner sc=new Scanner(System.in);
	int t=sc.nextInt();
	for(int i=0;i<t;i++)
	{
		long a=sc.nextLong();
		long b=sc.nextLong();
		long number=1;
		long c=a;
		if(b*b>=a) {number=0;}//不可能的情况,最小边大于可能拼成的情况
		else {
		for(int j=0;j<index;j++)
		{
			if(c==0||prime[j]>c) {break;}//超出界,跳出
			long team=0;
		    while(c%prime[j]==0)
		    {
		    	c/=prime[j];team++;
		    }
		    number*=(1+team);//计算
		}	
		if(c>1)number*=2;
		number/=2;
		//这里别被绕进去。这里不是按照次幂计算的,而是按照实打实的一个一个数判断的。
		for(int j=1;j<b;j++)
		{
			if(a%j==0)number--;
		}
		}
		System.out.println("Case "+(i+1)+": "+number);
	}
}

}
复制代码

欧拉筛:

import java.util.Scanner;

public class testC {
  static int index=0;
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		int prime[] = new int[100001];// 记录第几个prime
		int index = 0;
		boolean isprime[] = new boolean[1000001];
		for (int i = 2; i < 1000001; i++) {
			if (!isprime[i]) {
				prime[index++] = i;
			}
			for (int j = 0; j < index && i * prime[j] < 1000001; j++) {
				isprime[i * prime[j]] = true;// 找到的素数的倍数不访问
				if (i % prime[j] == 0)
					break;// 关键!!!!
			}
		}
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		for(int i=0;i<t;i++)
		{
			long a=sc.nextLong();
			long b=sc.nextLong();
			long number=1;
			long c=a;
			if(b*b>=a) {number=0;}//不可能的情况,最小边大于可能拼成的情况
			else {
			for(int j=0;j<index;j++)
			{
				if(c==0||prime[j]>c) {break;}
				long team=0;
			    while(c%prime[j]==0)
			    {
			    	c/=prime[j];team++;
			    }
			    number*=(1+team);
			}	
			if(c>1)number*=2;
			number/=2;
			for(int j=1;j<b;j++)
			{
				if(a%j==0)number--;
			}
			}
			System.out.println("Case "+(i+1)+": "+number);
		}
	}
}
复制代码

欧拉函数

求欧拉函数代码的方式:直接求和打表 欧拉函数的作用:一个数n,求小于n的互质的个数。特例:1——oula(1)=1; 欧拉函数的公式:

在这里插入图片描述
其中i为x所有质因数。注意:每种质因数只一个 为什么会这样?首先,互质的两个数一定不能有公共因数。比如9和7互质,9和12不互质,因为有共同因数3.

那么我难道需要一个个循环比较吗?

答案先然不可能,因为如果数值过大这是个很大的复杂度。那么我该如何处理?

换一种思维。比如求24中的互质个数。答案是1,5,7,11,13,17,19,23。共8个

  1. 24=2 * 2 * 2 * 3;那么在小于12中的数的核心共同质数为2的倍数或者三的倍数。有人可能说明明还要4,6的倍数,那是因为这些倍数囊括在2,3之中。所以我们每个质因数只记录一个
  • 看在24中,有1/2的是2的倍数,也就是1/2的数是和24有共同因数2.那么就有(1-1/2)的数和24没有共同因数2;
  • 同理那么就有1/3的数和24有共同因数3,并且(1-1/3)=2/3的数没有共同因数3.那么没有因数2和因数三剩下的不就是和24互质么,那么概率=(1-1/2) *乘以 (1-1/3)=1/3.总个数为24 *乘以 1/3=8满足要求。
  • 2. 如果一个因数出现多次怎么排除呢。或者怎么防止4,6这些数被计入因数中,这就要用到**质因数分解的思想**。只不过我们不需要这个幂出现的次数,只需要让剩余的不可能在存在当前这个数为因数的可能性。

    附上直接求代码:

    	private static int oula(int team) {
    		int i=0;int res=team;int team1=team;
    		for(i=2;i<(int)Math.sqrt(team1)+1;i++)
    		{
    			if(team%i==0) {
    				res=res/i*(i-1);
    				while(team%i==0) {team/=i;}//保证没有i作为因子			
    			}
    		}
    		if(team>1)res=res/team*(team-1);//说明后面还有一个比较大的互质因数大小为team
    		return res;
    	}
    复制代码

    其中,res为结果,team1作为求因数用。如果实在不能理解,好好看下质因数分解。

    打表代码:

           int a[]=new int[1000001];
           for(int i=1;i<1000001;i++)
           {
        	   a[i]=i;
           }
           for(int i=2;i+2<1000001;i+=2)
           {
        	   a[i]/=2;
           }
           for(int i=3;i+2<1000001;i+=2)
           {
        	   if(a[i]==i)
        	   {
        		   for(int j=i;j+i<=1000001;j+=i)
        		   {
        			   a[j]=a[j]/i*(i-1);
        		   }
        	   }
           }
    复制代码

    例题

    欧拉函数/素数判定

    题目链接

    题目

    Bamboo Pole-vault是Xzhiland的一项大受欢迎的运动。 Phi-shoe大师是他成功的非常受欢迎的教练。他需要为他的学生提供一些竹子,所以他让他的助手Bi-Shoe去市场购买。市场上有很多可能的整数长度的Bamboos(是的!)。根据Xzhila的传统,

    竹子的分数=Φ(竹子的长度)

    (Xzhilans非常喜欢数论)。对于您的信息,Φ(n)=小于n的数字,它们相对于素数(除了1之外没有公约数)到n。因此,长度为9的竹子的得分为6,因为1,2,4,5,7,8是9的相对素数。

    助理双鞋必须为每个学生买一个竹子。作为一个扭曲,Phi-shoe的每个撑杆跳学生都有一个幸运数字。 Bi-shoe希望购买竹子,这样他们每个人都会得到一张分数大于或等于他/她的幸运数字的竹子。 Bi-shoe希望最大限度地减少购买竹子所花费的总金额。一个竹子单位花费1 Xukha。帮助他

    输入 输入以整数T(≤100)开始,表示测试用例的数量。

    每个案例都以包含整数n(1≤n≤10000)的行开头,表示Phi-shoe的学生人数。下一行包含n个空格分隔的整数,表示学生的幸运数字。每个幸运数字将位于[1,106]范围内。

    输出 对于每种情况,打印案例编号和购买竹子所花费的最少金额。有关详细信息,请参阅示例 Sample Input 3 5 1 2 3 4 5 6 10 11 12 13 14 15 2 1 1 Sample Output Case 1: 22 Xukha Case 2: 88 Xukha Case 3: 4 Xukha

    题意

    题意:给你n个整数,第i个整数为Xi。定义phi(k)为k的欧拉函数值,设pi为满足phi(pi)>=Xi的最小整数,题目就是要求sum(p1,p2,p3,...,pn)。

    告诉你幸运数字x,你找出phi(n)=x的这个最小的n,若干个这样数的合。

    首先要清楚几个概念phi(n)=n-1,==n为素数==时候。因为n和小于它的任意都互质。 所以解题思路大致有两个:

    欧拉函数的角度:

    欧拉是最明显的,要找出大于这个数最小的那个phi[i],如果==单个欧拉函数求会TL==所以需要欧拉打表。没输入一个数网上找几个就行了

    素数角度

    n为素数时候,phi(n)=n-1,所以第一个phi(i)=t的那个i就是在t右侧的第一个素数。有了这个思路你就可以用素数解决问题,可以用素数筛。用直接的素数判定也能过。 c++代码: 直接判定

    #include <iostream>
    #include<stdio.h>
    using namespace std;
    #define ll long long
    bool isprime(int index)
     {
    		if(index<=2)return true;
    		else {
    			for(int i=2;i*i<index+1;i++)
    			{
    				if(index%i==0)return false;
    			}
    			return true;
    		}
     }
    int main()
    {
    
           int t;cin>>t;
           for(int i=0;i<t;i++)
           {
        	   int n;cin>>n;ll count=0;
        	   for(int j=0;j<n;j++)
        	   {
        		   ll team;
        		   cin>>team;
        		   int index=team+1;
        		   while(!isprime(index))
                    {index++;}
        		   count+=index;
    
        	   }
        	   //string s=" Xukha";
        	    printf("Case %d: %lld Xukha\n",(i+1),count);
           }
           return 0;
    
    }
    复制代码

    欧拉筛

    #include <iostream>
    #include<stdio.h>
    using namespace std;
    #define ll long long
    const int MAXN=1100000+7;
    int m;
    ll a[MAXN],euler[MAXN];
    void phi()
    {
        for(int i=1;i<=m;i++)
        a[i]=i;
        for(int i=2;i<=m;i+=2)
        a[i]>>=1;
        for(int i=3;i<=m;i++)
        {
            if(a[i]==i)
            {
                for(int j=i;j<=m;j+=i)
                a[j]=(a[j]/i)*(i-1);
            }
        }
    }
    int main()
    {
             m=1100000;
             phi();
           int t;cin>>t;
    
           for(int i=0;i<t;i++)
           {
               ll n,count;
        	   cin>>n;count=0;
        	   for(int j=0;j<n;j++)
        	   {
        		   ll team;
        		   cin>>team;
        		   int index=team+1;
        		   while(a[index]<team)
                    {index++;}
        		   count+=index;
        	   }
        	    printf("Case %d: %lld Xukha\n",(i+1),count);
           }
           return 0;
    
    }
    复制代码

    java 欧拉打表(可以自己改成素数)

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.OutputStreamWriter;
    import java.io.PrintWriter;
    import java.io.StreamTokenizer;
    import java.util.Scanner;
    public class Main{
    	public static void main(String[] args) throws IOException {
    		// TODO 自动生成的方法存根
    		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
           in.nextToken();int t=(int)in.nval;
           int a[]=new int[1100001];
           for(int i=1;i<1100001;i++)
           {
        	   a[i]=i;
           }
           for(int i=2;i+2<1100001;i+=2)
           {
        	   a[i]/=2;
           }
           for(int i=3;i+2<1100001;i+=2)
           {
        	   if(a[i]==i)
        	   {
        		   for(int j=i;j+i<=1100001;j+=i)
        		   {
        			   a[j]=a[j]/i*(i-1);
        		   }
        	   }
           }
      
           for(int i=0;i<t;i++)
           {
        	   in.nextToken();int n=(int)in.nval;long count=0;
        	   for(int j=0;j<n;j++)
        	   {
        		   in.nextToken();
        		   long team=(long)in.nval;
        		   int index=(int) (team+1);
        		   while(a[index]<team) {index++;}
        		   count+=index;
        		   //System.out.println(oula(team));
        	   }
        	   System.out.println("Case "+(i+1)+": "+count+" Xukha");
           }
    	}
    
    	private static boolean isprime(int index) {
    		if(index<=2)return true;
    		else {
    			for(int i=2;i*i<index+1;i++)
    			{
    				if(index%i==0)return false;
    			}
    			return true;
    		}
    		
    	}
    
    	private static int oula(int team) {
    		int i=0;int res=team;int team1=team;
    		for(i=2;i<(int)Math.sqrt(team1)+1;i++)
    		{
    			if(team%i==0) {
    				res=res/i*(i-1);
    				while(team%i==0) {team/=i;}//保证I是素数				
    			}
    		}
    		if(team>1)res=res/team*(team-1);
    		return res;
    	}
    }
    复制代码

    在这里插入图片描述

    github一些刷题代码

    个人公众号:bigsai

    关注下面的标签,发现更多相似文章
    评论