首页 > 代码库 > Uva 10892 LCM Cardinality (数论/暴力)
Uva 10892 LCM Cardinality (数论/暴力)
题意:给出数n,求有多少组A,B的最小公约数为n;
思路:3000ms,直接暴力寻找,找到所有能把n整除的数 pi, 枚举所有pi
代码:
#include <iostream> #include <cstdio> #include <vector> #define ll long long using namespace std; ll gcd(ll a,ll b) { if(b==0) return a; else return gcd(b,a%b); } int main() { ll n; while(cin>>n&&n) { vector <ll> p; for(ll i=1; i*i<=n; i++) { if(n%i==0) { p.push_back(i); if(n/i!=i) p.push_back(n/i); } } int ans=0; for(ll i=0; i<p.size(); i++) { for(ll j=i; j<p.size(); j++) { if((p[i]*p[j]/gcd(p[i],p[j]))==n) ans++; } } printf("%lld %d\n",n,ans); } return 0; }
Uva 10892 LCM Cardinality (数论/暴力)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。