记录几个简单数论题

本文从WordPress迁移而来, 查看全部WordPress迁移文章

uva 10892 LCM Cardinality

给出n,有多少对(a,b)使得a与b的lcm是n,其中(a,b),(b,a)视为一对

找出n所有的约数,枚举两个约数,L <= R, 计算lcm(L,R) = n 则计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long
#define PII pair<int,int>
#define MP make_pair
#define PB push_back
#define CL(xx,yy) memset((xx),(yy),sizeof((xx)))

vector<PII>fa;
vector<int>number;

void work(int n){
fa.clear();
int lim = (int)sqrt(n+0.5);
for(int f = 2; n > 1 && f <= lim; f++){
if(n % f == 0){
int cnt = 0;
while(n % f == 0 && n > 1){
n /= f; cnt++;
}
fa.PB(MP(f,cnt));
}
}
if(n > 1) fa.PB(MP(n,1));

//for(int i = 0; i < fa.size(); i++)
// printf("%d %d\n",fa[i].first , fa[i].second);
}

int POW(int f,int m){
int res = 1;
for(int i = 0; i < m; i++)
res *= f;
return res;
}

void dfs(int c,int s){
if(c >= fa.size()){
number.PB(s);
return ;
}
int f = fa[c].first;
int m = fa[c].second;
for(int i = 0; i <= m; i++){
int ss = POW(f,i);
dfs(c+1,ss*s);
}
}

void DO(){
number.clear();
dfs(0,1);
sort(number.begin(),number.end());
//for(vector<int>::iterator it = number.begin(); it != number.end(); it++)
// printf("%d ",*it);
//puts("");
}

int gcd(int a,int b){
if(b == 0) return a;
return gcd(b , a%b);
}

int LCM(int a,int b){
int g = gcd(a,b);
return a / g * b;
}

int solve(int n){
int ans = 0;
int size = number.size();
for(int r = 0; r < size; r++){
int R = number[r];
for(int l = 0; l < r; l++){
int L = number[l];
int lcm = LCM(L,R);
if(lcm == n){ /*printf("%d %d\n",L,R);*/ ans++; }
}
}
ans++;
return ans;
}

int main(){
int n,ans;
while(scanf("%d",&n)!=EOF && n){
work(n);
DO();
ans = solve(n);
printf("%d %d\n",n,ans);
}
return 0;
}

其他OJ : http://218.5.5.242:9018/JudgeOnline/problem.php?id=1111

A与B的gcd是x,设
A = x * a

B = x * b

a与b一定互质

A与B的lcm是y,则

x a b = y

a * b = y / x = n

所以a和b都是n的因数,且a与b互质,一个二次循环暴力枚举即可

(a,b)(b,a)视为两组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long
#define PII pair<int,int>
#define MP make_pair
#define PB push_back
#define CL(xx,yy) memset((xx),(yy),sizeof((xx)))

vector<PII>fa;
vector<int>number;

void work(int n){
fa.clear();
int lim = (int)sqrt(n+0.5);
for(int f = 2; n > 1 && f <= lim; f++){
if(n % f == 0){
int cnt = 0;
while(n % f == 0 && n > 1){
n /= f; cnt++;
}
fa.PB(MP(f,cnt));
}
}
if(n > 1) fa.PB(MP(n,1));

//for(int i = 0; i < fa.size(); i++)
// printf("%d %d\n",fa[i].first , fa[i].second);
}

int POW(int f,int m){
int res = 1;
for(int i = 0; i < m; i++)
res *= f;
return res;
}

void dfs(int c,int s){
if(c >= fa.size()){
number.PB(s);
return ;
}
int f = fa[c].first;
int m = fa[c].second;
for(int i = 0; i <= m; i++){
int ss = POW(f,i);
dfs(c+1,ss*s);
}
}

void DO(){
number.clear();
dfs(0,1);
sort(number.begin(),number.end());
//for(vector<int>::iterator it = number.begin(); it != number.end(); it++)
// printf("%d ",*it);
//puts("");
}

int GCD(int a,int b){
if(b == 0) return a;
return GCD(b , a%b);
}

int solve(int n){
int ans = 0;
int size = number.size();
for(int l = 0; l < size; l++){
int L = number[l];
for(int r = 0; r < size; r++){
int R = number[r];
int gcd = GCD(L,R);
if(gcd != 1) continue;
LL s = L*R;
if(s == (LL)n) ans++;
}
}
return ans;
}

int main(){
int x,y,n,ans;
while(scanf("%d%d",&x,&y)!=EOF){
if(y % x != 0){ puts("0"); continue; }
n = y / x;
work(n);
DO();
ans = solve(n);
printf("%d\n",ans);
}
return 0;
}

hdu 4497

题意:给出gcd和lcm,问存在多少种x,y,z,使得它们的gcd和lcm和给出的数值相等,例如(1,1,2),(1,2,1),(2,1,1)算3种情况

从质因子的角度分析,就拿sample 1来说

6 = 2 x 3
72 = 2^3 x 3^2

  1. 对于质因子2,可以确定,x,y,z,分解出来的2的个数都一定 >= 1 , 如果三者中有其中一个分解出来的2的个数小于1,最后gcd会小于6
  2. 对于质因子2,可以确定,x,y,z中至少存在一个,分解出来的2的个数 = 1,否则的话,x,y,z分解出来的2的个数都大于1,最后gcd会大于6
  3. 对于质因子2,可以确定x,y,z分解出来的2的个数都一定 <= 3 , 如果三者中有其中一个分解出来的2的个数大于3,最后lcm会大于72
  4. 对于质因子2,可以确定x,y,z中,至少存在一个,分解出来的2的个数 = 3,否则的话,x,y,z分解出来的2的个数都小于3,最后lcm会小于72

假设x,y,z分别分解出nx,ny,nz个2,nx,ny,nz都减掉1个2(表示约掉gcd里面的那一个2),变为nxx,nyy,nzz

可以知道nxx,nyy,nzz中至少有一个为1-1=0,至少有一个为3-1=2(这是根据前面的分析得到的,至少存在一个分解2的个数为1,减掉了1个就是0;至少存在一个分解2的个数为3,减掉1个就是2)

那么可以分为3种种类

1
2
3
0 0 2
0 2 2
0 1~1 2

推广开,如果这个质因子最多的个数为r,可分为3类

1
2
3
0 0 r
0 r r
0 1~r-1 r

又因为(1,1,2),(1,2,1)被视为不同的答案,那么要考虑排列

1
2
3
0 0 r , 0 r 0 , r 0 0 3种
0 r r , r 0 r , r r 0 3种
0 1~r-1 r , 6 * (r-1)种

一共 3 + 3 + 6 (r-1) = 6 r 种

所以对于一种因子,能产生6 * r种可能,每种因子都是这样算,最后乘法原理

例子:

gcd = 18 = 2^1 x 3^2

lcm = 6912 = 2^4 x 3^3 x 4^2

对于因子2,r = 4-1 = 3,产生 6 * 3 = 18种

对于因子3,r = 3-2 = 1,产生 6 * 1 = 6种

对于因子4,r = 2-0 = 2,产生 6 * 2 = 12种

最后答案 18 6 12 = 1296

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long
#define PII pair<int,int>
#define MP make_pair
#define PB push_back
#define CL(xx,yy) memset((xx),(yy),sizeof((xx)))

vector<PII>fl,fg,fa;
vector<int>number;
struct elem{
int a,b,c;
};

void work1(int n){
fl.clear();
int lim = (int)sqrt(n+0.5);
for(int f = 2; n > 1 && f <= lim; f++){
if(n % f == 0){
int cnt = 0;
while(n % f == 0 && n > 1){
n /= f; cnt++;
}
fl.PB(MP(f,cnt));
}
}
if(n > 1) fl.PB(MP(n,1));
}

void work2(int n){
fg.clear();
int size = fl.size();
for(int i = 0; i < size; i++){
int f = fl[i].first;
int cnt = 0;
while(n % f == 0){
n /= f; cnt++;
}
fg.PB(MP(f,cnt));
}
}

void DO(){
fa.clear();
for(int i = 0; i < fl.size(); i++){
fa.PB(MP(fl[i].first , fl[i].second-fg[i].second));
}
}

int solve(){
int ans = 1;
for(int i = 0 ; i < fa.size(); i++){
if(fa[i].second > 0)
ans *= (6*fa[i].second);
}
return ans;
}

int main(){
int CASE;
scanf("%d",&CASE);
while(CASE--){
int G,L,n;
scanf("%d%d",&G,&L);
if(L % G != 0LL) { puts("0"); continue; }
work1(L);
work2(G);
DO();
int ans = solve();
printf("%d\n",ans);
/*
for(int i = 0; i < fl.size(); i++)
printf("%d[%d] ",fl[i].first , fl[i].second);
puts("");
for(int i = 0; i < fg.size(); i++)
printf("%d[%d] ",fg[i].first , fg[i].second);
puts("");
for(int i = 0; i < fa.size(); i++)
printf("%d[%d] ",fa[i].first , fa[i].second);
puts("");
*/
}
return 0;
}