数学

質問リンク

https://www.acmicpc.net/problem/1565

質問する

に答える

Dの中のすべての数の倍数を求め、Mの中のすべての数の約数因数を求めればよいので、まずDの最小公倍数とMの最大公倍数を求めた.
最大公約数のすべての約数はM中のすべての数の約数であるため,最終的にMの最大公約数の約数の中でDの最小公倍数の倍数係数を探すことが問題である.
弱数アルゴリズムを求めることにより,各弱数をlcm(最小公倍数)で割ってcnt++とし,その値を求める.

試行錯誤

求約数アルゴリズムでは,符号化エラーにより93%で何度もエラーが発生した.
△オーバーフローの問題かと思ったら、変なところしか修理していなかったので、ずっと間違いがあった!

コード#コード#

#include <iostream>
using namespace std;
typedef long long ll;
ll D[51], M[51];
ll vlcm, vgcd;
ll gcd(ll a, ll b) {
	while (b != 0) {
		ll r = a % b;
		a = b;
		b = r;
	}
	return a;
}

ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int d, m;
	cin >> d >> m;
	for (int i = 0; i < d; i++) cin >> D[i];
	for (int i = 0; i < m; i++) cin >> M[i];

	vgcd = M[0];//최대공약수
	for (int i = 1; i < m; i++) vgcd = gcd(vgcd, M[i]);

	vlcm = 1;//최소공배수
	for (int i = 0; i < d; i++) {
		vlcm = lcm(vlcm, D[i]);
		if (vlcm > vgcd || vlcm == 0) {
			cout << 0;
			return 0;
		}
	}

	ll i, cnt = 0;
	for (i = 1; i*i < vgcd; i++) {
		if (vgcd%i == 0) {
			if (i%vlcm == 0) cnt++;
			if ((vgcd / i) % vlcm == 0) cnt++;
		}
	}
	if (i*i == vgcd && (i%vlcm == 0)) cnt++;
	cout << cnt;
}

ポスト

注目すべきリンク
https://m.blog.naver.com/PostView.nhn?blogId=soohan530&logNo=221029295310&proxyReferer=https:%2F%2Fwww.google.com%2F
約数アルゴリズム
https://m.blog.naver.com/PostView.nhn?blogId=writer0713&logNo=221133124302&proxyReferer=https:%2F%2Fwww.google.com%2F
最大公約数最小公倍数アルゴリズム