codeforces 1349A（数学）
原创codeforces 1349A（数学）
原创
题意描述
思路
题意要求求出gcd(lcm(a_{i},a_{j})) | i<j，由于lcm(a_{i},a_{j})=a_{i}*a_{j}/gcd(a_{i},a_{j})，故得到式子gcd(a_{i}*a_{j}/gcd(a_{i},a_{j}))。接下来对式子进行化简。
gcd(a_{i}*a_{j}/gcd(a_{i},a_{j}))
=a_{i}*gcd(a_{j}/gcd(a_{i},a_{j}))
=a_{i}*gcd(a_{j})/gcd(gcd(a_{i},a_{j}))
=a_{i}*gcd(a_{j})/gcd(a_{i},gcd(a_{j}))
关于化简步骤的证明
第一步到第二步：
gcd(a*k_{i})=a*gcd(k_{i})，1≤i≤n
显然，无论i取何值，a都是a*k_{i}的公因子，故gcd(a*k_{i})=a*gcd(k_{i})，1≤i≤n
即gcd(a_{i}*a_{j}/gcd(a_{i},a_{j}))=a_{i}*gcd(a_{j}/gcd(a_{i},a_{j}))，1≤i≤n
第二步到第三步：
gcd(a_{i}/b_{i})=gcd(a_{i})/gcd(b_{i})，1≤i≤n
保证a_{i}整除b_{i}
移项得gcd(a_{i}/b_{i})*gcd(b_{i})=gcd(a_{i})，1≤i≤n
因为保证a_{i}整除b_{i}，故两部分a_{i}/b_{i}和b_{i}最大公约数的成绩一定与gcd(a_{i})相同。
即a_{i}*gcd(a_{j}/gcd(a_{i},a_{j}))=a_{i}*gcd(a_{j})/gcd(gcd(a_{i},a_{j}))，1≤i≤j≤n。
这样就可以扫一遍数组来记录下来每一个部分的最大公约数。
AC代码
#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=2*1e5+10;
const int M=1e6+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
/*
独立思考
不要看测试样例
找性质
试着证明
写完后不盲目交
*/
ll a[N],ggcd[N];
void solve(){
int n;cin>>n;
rep(i,1,n+1) cin>>a[i];
ll ans=0;
rep(i,1,n+1){
ggcd[i]=__gcd(a[i],ggcd[i-1]);
ans=__gcd(a[i]*ggcd[i-1]/ggcd[i],ans);
}
cout<<ans<<endl;
}
int main(){
IOS;
//freopen("test.txt", "r", stdin);
//freopen("test.txt", "w", stdout);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。