基础算法题——呼兰河传（除法不可直接求余）

逃离我推掉我的手 2022-11-21 14:56 22阅读 0赞

#### [呼兰河传][Link 1] ####

题目描述  
沿着河边看一看清冷的夏夜，耳机里是AR的《呼兰河传》。AR的呼兰河并非一条河，而是一个故乡小城的生活日记。静谧的童年，孩子看世界的眼光，花开鸟飞间的自由，塑造了一方那个时代中少有的美好。现在，你需要回答以下问题，才可倾听这首《呼兰河传》带来的温柔，试试吧。给你n个数，选择一些数，使得LCM最大，输出LCM的最大值并对1e9+9取模。  
LCM：最小公倍数

输入描述:  
第一行输入一个n，代表数字的个数。  
第二行输入n个数a\[i\]，代表每个数的值。  
1<=n<=1e6,1<=a\[i\]<=1e5。

输出描述:  
选择一些数能得到的最大LCM，由于LCM太大了，你只需要对1e9+9取模即可。  
示例1  
输入  
3  
1 2 3  
输出  
6  
说明  
选择2和3的LCM最大，为6

--------------------

**除法不可直接求余！  
除法不可直接求余！  
除法不可直接求余！**  
在赛中就直接将全部数进行求公倍数，中间不断求余，忽略了gcd函数中除法，哎~

#include<stdio.h>
    #define ll long long
    const ll mod=1e9+9;
    
    ll gcd(ll a, ll b){ 
    	if(a%b==0) return b;
    	return gcd(b, a%b);
    }
    
    int main(){ 
    	ll a, b, n, ans;
    // freopen("data.txt", "r", stdin);
    	scanf("%lld%lld", &n, &ans);
    	for(int i=1; i<n; i++){ 
    		scanf("%lld", &a);
    		b = gcd(ans, a);
    		ans = ((ans/b)*a)%mod;
    	}
    	printf("%lld", ans);
    	return 0;
    }

--------------------

#### 正解：对每个数字进行质因数分解，统计每个质因数累乘次数的最大值，最后相乘即可。 ####

#### 思考：为什么这里是统计每个质因数累乘次数的最大值？ ####

答：题目所求的是最小公倍数，其他质因数都将会被约掉。  
**例如**  
40 质因数分别是 2、2、2、5  
45 质因数分别是 2、2、2、2、3  
它们的公倍数是多少呢？  
是240，质因数 2 的数量是最大的取 4 个与 40 中 3 个 2 毫无关系，因为 40 中的质因数 2 并不是最大。同理，质因数 3 的最大数量是 1 ，质因数 5 的最大数量是 1，其他质因数都为 0。  
***计算式：240 = 24 \* 3 \* 5***

**接着我们很容易发现 质因数都是素数**

--------------------

#### 具体解题步骤： ####

①、初始化求出 1 ~ 100010 以内的素数，并记录下来。  
②、将 n 个数进行质因数分解，统计每个质因数累乘次数的最大值，这里也需要一点小技巧，直接暴力，时间超时。

// num：100010内素数的个数
    // prime[]：素数的集合
    // pow_[]：统计每个素数的最大指数
    for(int i=0; i<n; i++){ 
    	scanf("%lld", &a);
    	//缩小判断范围：prime[j]*prime[j]<=a
    	//下面需要加特判 
    	for(int j=0; prime[j]*prime[j]<=a&&j<num; j++){ 
    		ll cur=0;
    		while(a%prime[j]==0){ 
    			a /= prime[j];
    			cur++;
    		}
    		pow_[prime[j]] = max(pow_[prime[j]], cur);
    	}
    	// 特判，可能存在一个在上述范围内约不掉的质因数 
    	if(a>1) pow_[a] = max(1LL, pow_[a]);
    }

③、乘法能直接求余，快速幂+求积+求余，得出答案。

--------------------

整合代码

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const ll mod=1e9+9;
    ll prime[100010], num=0;
    ll pow_[100010];
    ll quick(int base, int power){ 
    	ll ans = 1;
    	while(power){ 
    		if(power&1) ans = (ans*base)%mod;
    		base = (base*base)%mod;
    		power >>= 1;
    	}
    	
    	return ans;
    }
    
    void init(){ 
    	bool judge[100010]={ false};
    	judge[1]=true;
    	for(int i=1; i<=100010; i++){ 
    		if(judge[i]==false)
    			prime[num++] = i;
    		
    		for(int j=0; prime[j]*i<=100010&&j<num; j++){ 
    			judge[i*prime[j]] = true;
    			if(i%prime[j]==0)
    				break;
    		}
    	}
    }
    
    int main(){ 
    	ll a, b, n, ans;
    // freopen("data.txt", "r", stdin);
    	scanf("%lld", &n);
    	init();
    	for(int i=0; i<n; i++){ 
    		scanf("%lld", &a);
    		//缩小判断范围：prime[j]*prime[j]<=a
    		//下面需要加特判 
    		for(int j=0; prime[j]*prime[j]<=a&&j<num; j++){ 
    			ll cur=0;
    			while(a%prime[j]==0){ 
    				a /= prime[j];
    				cur++;
    			}
    			pow_[prime[j]] = max(pow_[prime[j]], cur);
    		}
    		// 特判，可能存在一个约不掉的质因数 
    		if(a>1) pow_[a] = max(1LL, pow_[a]);
    	}
    	
    	ans = 1;
    	for(int i=0; i<num; i++)
    		ans = ans*quick(prime[i], pow_[prime[i]])%mod;
    	printf("%lld", ans);
    	return 0;
    }

[Link 1]: https://ac.nowcoder.com/acm/contest/6037/E