记录几个简单数论题

本文从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;
}