(1+p2)写(1)只是因预感到当时首没法写多深入……

题意:给定n求,有n个因子的极其小刚好整数。

题解:水题,zcr都见面,我虽非说啊了。

  以勤个数球求法应该明了,将m分解质因数,然后发现
a1^p1*a2^p2….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)只是盖预感到马上首没法写多深入……


互质

假定个别单正整数互质,那就是印证这简单只数最大公约数为1
写成式子的口舌虽是只要gcd(a,b)=1,则a和b互质

叫有一个正好整数n,怎么要1及n的正整数吃,与n互质的屡屡的个数?

要这个个数为phi(n)

①如果n=1

很明显phi(1)=1啊

②如果n为质数

依据质数的“质数只出1同他自两单因数”的概念,此时有phi(n)=n-1=n ( 1 – 1
/ n ),因为1暨n-1都跟n互质啊

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

根据质数的定义,n的兼具因数为:1、p 、 p * p、 p * p * p、 …… 、
p^q,
所以于随意因数里没有p的正整数m,就生出m和n互质,
于是1到p的频繁里就出p不跟n互质,
p+1到2 * p 的反复里才发生2 * p 不与n互质,
……

于是1交n里,p分之一的数不跟n互质
据此这phi(n)=n( 1 – 1 / p )耶

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

拿1及n的整数表示为i*a+ j( j < a )的形式
顺手又将1顶n的多次排成一个a * b的矩阵

bet365娱乐场官网 1

哎呀这里得动一下最大公约数的一个性:gcd(a+b,b)=gcd(a,b)
遂就见面发觉,如果0 * a + j 与a互质,那么0 * a + j
这同一整列的数就还同a互质了
用就是,这phi(a)除以a的余数和a互质的高频,和a互质,剩下的还不和a互质

接下来研究这phi(a)列数里那些跟b互质
对此各一样排列的b个数,

bet365娱乐场官网 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小

因此就同样排的b个数里不有除以b余数相同之鲜只数
也就是说这无异列的b个数里,除以b余数为0顶b-1的一再,每种余数的再三都正好有1只!
也就是说每一样排列的b个数里,与b互质的累累,就是phi(b)个!

所以1暨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是除1缘外随便一个恰好整数

在这种状况下,n可以拓展抵押因数分解,就是说n可以发表为
n=(a1^p1) * (a2^p2) * … * (ak^pk)
(p1到pk为不同的质数,a1及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)
哦这即是欧拉函数的通式。

bet365娱乐场官网 3

通式!x=(a1^p1) * (a2^p2) * … * (ak^pk)
(p1到pk为歧之质数,a1交ak为正整数)

小结一下即便是,phi(x)就是1到x底正整数吃,与x互质的屡屡之个数。

(毕竟是(1)……只说“证明过程”也从未问题之啦)

相关文章