求正整数

题意:给定n求,有n个因子的微小正整数。

题解:水题,zcr都会,笔者就不说什么样了。

  因数个数球求法应该领会,将m分解质因数,然后发现
a1^p1*a贰^p贰….an^pn那样一个姿态,

  (1+p1)*(1+p2)*…=n,然后用小的质数填坑。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int pri[] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
 5 int n, ans[100005], res[21], tmp[21];
 6 double lg[21], mn=DBL_MAX;
 7 
 8 void input()
 9 {
10     scanf("%d", &n);
11     for(int i=1; i<=16; i++) lg[i] = log(pri[i]);
12 }
13 
14 void dfs(double x, int y, int z){//现在的数是e^x,还剩下y个因子,选到第z个质数
15     if(x >= mn) return;
16     if(y == 1){
17         mn = x;
18         memset(res, 0, sizeof(res));
19         for(int i=1; i<=z-1;i++) res[i]=tmp[i];
20         return;
21     }
22     if(z>16) return;
23     for(int i = 0; (i+1)*(i+1)<=y; i++){
24         if(y%(i+1)==0)
25         {
26             if(i != 0){
27                 tmp[z] = i;
28                 dfs(x+lg[z]*i, y/(i+1), z+1);
29             }
30             if((i+1)*(i+1)!=y){
31                 tmp[z] = y/(i+1)-1;
32                 dfs(x+lg[z]*(y/(i+1)-1), i+1, z+1);
33             }
34         }
35     }
36 }
37 
38 void work()
39 {
40     dfs(0, n, 1);
41 }
42 
43 void output()
44 {
45     ans[0]=ans[1]=1;
46     for(int i=1;i<=16;i++){
47         for(;res[i]>0;res[i]--){
48             for(int j=1;j<=ans[0];j++) ans[j]*=pri[i];
49             for(int j=1;j<=ans[0];j++) ans[j+1]+=ans[j]/10, ans[j]%=10;
50             if(ans[ans[0]+1]!=0) ans[0]++;
51             while(ans[ans[0]]/10!=0){
52                 ans[ans[0]+1] += ans[ans[0]]/10;
53                 ans[ans[0]] %= 10;
54                 ++ans[0];
55             }
56         }
57     }
58     for(int i = ans[0]; i>=1; i--){
59         printf("%d", ans[i]);
60     }
61     printf("\n");
62 }
63 
64 int main()
65 {
66     input();
67     work();
68     output();
69     return 0;
70 }

 

写(1)只是因为预知到那篇没办法写多少深度入……


互质

只要多个正整数互质,那就表明这七个数最大公约数为一
写成式子的话正是若gcd(a,b)=一,则a和b互质

付给一个正整数n,怎么求1到n的正整数中,与n互质的数的个数?

设这几个个数为phi(n)

①如果n=1

很明显phi(1)=1啊

②如果n为质数

依照质数的“质数唯有一和他自小编三个因数”的定义,此时有phi(n)=n-1=n ( 壹 – 1
/ n ),因为1到n-1都与n互质啊

③如果n=p ^ q (p为质数)

基于质数的定义,n的持有因数为:一、p 、 p * p、 p * p * p、 …… 、
p^q,
为此对于随意因数里未有p的正整数m,就有m和n互质,
于是乎一到p的数里只有p不与n互质,
p+1到2 * p 的数里惟有2 * p 不与n互质,
……

于是一到n里,p分之一的数不与n互质
就此这时phi(n)=n( 壹 – 壹 / p )耶

④如果n=a*b( a、 b互质 )

把1到n的整数表示为i*a+ j( j < a )的形式
附带再把1到n的数排成几个a * b的矩阵

图片 1

哎那里得利用一下最大公约数的一个属性:gcd(a+b,b)=gcd(a,b)
于是乎就会发觉,如若0 * a + j 与a互质,那么0 * a + j
这1整列的数就都和a互质了
据此正是,那phi(a)除以a的余数和a互质的数,和a互质,剩下的都不和a互质

接下来探讨这phi(a)列数里那三个和b互质
对于每壹列的b个数,

图片 2

有三个定论:不设有除以b余数相同的七个数

此处就不扯什么剩余系,直接反证法证吧:假设那一列数里面c * a + j和d * a

  • j除以b的余数相同,且0<=c<d<b,
    那便是说把它们多少个一减,获得的(d-c) * a就是b的倍数了
    而是a和b互质啊,那么(d-c)就得是b的倍数了,然而(d-c)又比b小

故此这1列的b个数里不存在除以b余数相同的多个数
也正是说那1列的b个数里,除以b余数为0到b-壹的数,每一种余数的数都正好有3个!
也正是说每壹列的b个数里,与b互质的数,正是phi(b)个!

从而壹到n中既与a互质,又与b互质的数,有phi(a) * phi(b) 个!
然后再用上a与b互质的条件,和互质的概念,
所以1到n中与a * b,约等于n,互质的数,有phi(a) * phi(b) 个!

phi(a*b)=phi(a) * phi(b) (a与b互质)

伍假设n是除一以外随便多少个正整数

在那种状态下,n能够拓展质因数分解,就是说n能够表达为
n=(a1^p1) * (a2^p2) * … * (ak^pk)
(p1到pk为分裂的质数,a一到ak为正整数)
的形式

利用③和④的结论,
phi(n)=phi(a1^p1) * phi(a2^p2) * … * phi(ak^pk)
=(a1^p1) * (a2^p2) * … * (ak^pk) * (1- 1/a1) * (1- 1/a2) * .. *
(1- 1/ak)
嗯这正是欧拉函数的通式。

图片 3

通式!x=(a1^p1) * (a2^p2) * … * (ak^pk)
(p壹到pk为差别的质数,a一到ak为正整数)

总计一下就是,phi(x)正是1到x的正整数中,与x互质的数的个数。

(究竟是(壹)……只讲“注明进度”也没难题的啦)

相关文章