第十二周总结

第十二周总结

一、知识总结
1，算术基本定理：对于每个整数n，都可以唯一分解成素数的乘积，如图所示：
n=p1p2p3…pk （ p1=<p2=<p3=<…=<pk）
n=p1^e1p2e2p3^e3…pkek(p1<p2<p3<…Pk且ei>0)

vector<int> factor(int x) {
	vector<int> ret;
	for (int i = 2; i * i <= x; ++i)
		while (x % i == 0) {
			ret.push_back(i);
			x /= i;
	}
	if (x > 1) ret.push_back(x);
	return ret;
 }

利用埃氏筛法可以快速实现素因数分解，只要在判定质数时记录下每个数值的最小素因数即可。算法实现如下：

#define maxn 1000000
bool isPrime[maxn+1];
int minFactor[maxn+1];	//记录每个数的最小素因数的数组

void eratos(int n)
{
	int i,j;
	isPrime[0] = isPrime[1] = false;
	minFactor[0] = minFactor[1] = -1;
	for(i = 2;i <= n; ++i) 
	{
			isPrime[i] = true;
			minFactor[i] = i;//初始化，表示还未找到最小的素因数
	}
    for(i = 2;i * i <= n; ++i) 
    { if(isPrime[i])
      {
		for(j = i * i;j <= n;j += i)
		{
			isPrime[j] = false;
			if(minFactor[j]==j) //如果此前尚未找到j的素因数，
				//那么将其设为i
				minFactor[j] = i; 
		}
	 }
   }
 }
   vector<int> factor(int x) 
   {
		vector<int> ret;
		while(x > 1)
		{
			ret.push_back(minFactor[x]);
			x /= minFactor[x];
		}
		return ret;
   }

2、最大公约数
。设 a,b是不都为 0的整数，c 为满足 c|a且c|b 的最大整数，则称c 是 a,b 的最大公约数，记为 gcd(a,b) 或 (a,b)。
。最大公约数有如下性质：
。gcd(a,b)=gcd(b,a)
。gcd(a,b)=gcd(-a,b)
。gcd(a,b)=gcd(|a|,|b|)
。若d|a且d|b，则d|gcd(a,b)
。gcd(a,0)=a
。gcd(a,ka)=a
。gcd(an,bn)=ngcd(a,b)
。gcd(a,b)=gcd(a,ka+b)
3、欧几里德定理（辗转相除法）
定理：gcd(a, b) = gcd(b, a % b)。
证明：a = kb + r = kb + a%b，则a % b = a - kb。令d为a和b的公约数，则d|a且d|b 根据整除的组合性原则，有d|(a-kb)，即d|(a%b)。
这说明如果d是a和b的公约数，那么d也一定是b和a%b的公约数，即两者的公约数是一样的，所以最大公约数也必定相等。
int gcd(int a, int b)
{ return b ? gcd(b, a%b) : a; }
4、同余
基本概念
。除法定理：
对于任何整数a和任何正整数 m，存在唯一整数 q和 r，满足 0=<r<m且 a=qm+r,其中q=[a/m] 为商, r=a mod m为余数。
。余数：我们把a 除以 所得的余数 r 记作a mod m 。
。同余：如果 a mod m= b mod m，即a,b 除以m 所得的余数相等，记作：a=b (mod m)
。若a=b(mod m) ，则 (a,m)=()b,m 。
。若a=b(mod m)，且d|m ，则a=b(mod d)。
5、费马小定理
若p为素数，且a和p互素，则可以得到 a^(p-1)=1(mod p)
。一般情况下，在 p是素数的情况下，对任意整数 a 都有 a^p=a(mod p) 。
。费马小定理应用： p是素数，a,p互素，则 a^b mod p= a^(b mod p) mod p。
。如 p=5,a=3,3^4=81=1(mod 5)
。又如 3²⁰⁴⁶⁼³(4511+2)=3^2 (mod 5)=4(mod 5)
6、欧拉定理
。在 p 不是素数的情况下，可以使用欧拉定理：对于和m 互素的a ，有： a^f(m)=1(mod m)
。如 m=10,a=3 时，f(10)=4, 3^4=81=1(mod 10)。
。当 m是素数时，f(m)=m-1，代入可得a^(m-1)=1(mod m)
。因此欧拉定理也可以看作是费马小定理的加强。
。a,m互素 (m>1)，可得：a^b (mod m)=a^(b mod f(m)) (mod m)
。如 3^2017= 3^(4504+1)=3(mod 10)
7、裴蜀定理（Bézout 定理）
。对任何整数 a,b，关于未知数 x和 y 的线性不定方程（称为裴蜀等式）：ax+by=c
方程有整数解（当且仅当c 是gcd(a,b) 的倍数）。裴蜀等式有解时必然有无穷多个解。
。 ax+by=c有解的充要条件为 gcd(a,b)|c 。
。一定存在 x,y 满足 ax+by=gcd(a,b)。
。推论：a,b 互素等价于ax+by=1 有解。
扩展欧几里得算法
。根据欧几里得算法，可得：ax+by=gcd(a,b)=gcd(b,a mod b)=bx’+(a mod b)y’
。其中 a mod b 为 a-[a/b]b，代入上式后，可得：bx’+(a mod b)y’=bx’+(a-[a/b]b)y’=ay’+b(x’-[a/b]y’)
。可以得出x,y和 x’,y’的关系:x=y’,y=x’-[a/b]y’
。边界情况分析：，ax’+by’=d (d=gcd(a,b)),当b=0 时，a 为gcd(a,b) ，当且仅当x’=1 时等式成立。 可以为任何值，为方便起见，设 y’=0。
。根据 x=y’,y=x’-[a/b]y’，可以倒推出x 和 y的多组解。
。有无穷组解，扩展欧几里得算法计算出来的解是其中一个特解 ，可以以下方式来获得其他解。
二、题目解决
1、

Everybody knows any number can be combined by the prime number.
Now, your task is telling me what position of the largest prime factor.
The position of prime 2 is 1, prime 3 is 2, and prime 5 is 3, etc.
Specially, LPF(1) = 0.

Input

Each line will contain one integer n(0 < n < 1000000).

Output

Output the LPF(n).

Sample Input

1
2
3
4
5

Sample Output

0
1
2
1
3

题意

每个素数在素数表中都有一个序号，1的序号是0,2的序号是1，（4是2的倍数，序号也是1），3的序号是2,5的序号是3，以此类推。

代码

#include<iostream>
#include<cstdio> 
using namespace std; 
const int maxn=1000010; 
int arr[maxn]; 
int main() 
{ arr[1]=0; 
  for(int i=2;i<maxn;i++) 
  { arr[i]=-1;}
  int num=0; 
  for(int i=2;i<maxn;i++) 
  { if(arr[i]==-1) 
    { num++;arr[i]=num; //之前没做过处理，是第num个素数
      for(int j=i;j<maxn;j+=i) 
      { arr[j]=num;}//i的倍数都和i一个值
    } 
  } 
  int n;
  while(~scanf("%d",&n)) 
  { printf("%d\n",arr[n]);} 
  return 0; 
}

2、

A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, … shows the first 20 humble numbers.
Now given a humble number, please write a program to calculate the number of divisors about this humble number.For examle, 4 is a humble,and it have 3 divisors(1,2,4);12 have 6 divisors.

Input

The input consists of multiple test cases. Each test case consists of one humble number n,and n is in the range of 64-bits signed integer. Input is terminated by a value of zero for n.

Output

For each test case, output its divisor number, one line per case.

Sample Input

4
12
0

Sample Output

3
6

代码

#include<iostream>
#include<cstdio> 
using namespace std; 
#define ll long long
const int maxn=1000010; 
int arr[maxn]; 
int main() 
{ ll n,sum;
  while(scanf("%lld",&n))
  { if(n==0) break;
    sum=1;
    for(ll i=2;i*i<=n;i++)
    { if(n%i==0)
      { int num=1;
        while(n%i==0)
        { n/=i;num++;}
        sum*=num;
      }
    }
    if(n>1) sum*=2;
    printf("%lld\n",sum);
  }
  return 0; 
}