#include<bits/stdc++.h>
using namespace std;
set<int>S;
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(nullptr);
int T;cin>>T;
for(int i=0;i<T;i++){
int n;cin>>n;
for(int _=0;_<n;_++){
int num;cin>>num;
S.insert(num);
}
int ans=0;
while(S.size()>1){
set<int>::iterator it=S.begin();
int p = *it;
it++;
for(;it!=S.end();it++){
if(gcd(p,*it)==1){
ans++;
}
}
S.erase(p);
}
cout<<"case #"<<i<<":\n"<<ans<<endl;
S.clear();
}
}
2957. 统计不同的最简真分数的个数
Andrew-Malcom
Li Dao
关键是如何去重
本来是想把分数最为一个有序二元组放入set中，重载小于运算符，set自带去重，但是速度太慢超时了。
超时代码如下：
include
using namespace std;
int T,n;
int a[1010];
struct Point
{
int xx,yy;
bool operator<(const Point& bb) const
{
if(xx!=bb.xx) return xx S;
int gcd(int aa,int bb)
{
if(aa\=bb) return 0;
return 1;
}
int main()
{
std::ios::sync_with_stdio(false);
cin>>T;
for(int step=0;step>n;
S.clear();
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
if(ok(a[i],a[j])) S.insert((Point){a[i],a[j]});
if(ok(a[j],a[i])) S.insert((Point){a[j],a[i]});
}
printf(“case #%d:\n%d\n”,step,S.size());
}
return 0;
}
后来发现，只要先把n个数排序，去重，这n个数没有重复了，产生的分数也不会重复
而且因为都是最简分数，不会出现1/2=2/4重复的情况
代码如下：
include
using namespace std;
int T,n;
vector a,b;
int gcd(int aa,int bb)
{
if(aa=bb) return 0;
return 1;
}
int main()
{
std::ios::sync_with_stdio(false);
cin>>T;
for(int step=0;step>n;
int ans=0;
a.clear();
for(int i=1;i<=n;i++)
{
int xx;
cin>>xx;
a.push_back(xx);
}
sort(a.begin(),a.end());
b.clear();
unique_copy(a.begin(),a.end(),back_inserter(b));
for(int i=0;i<b.size();i++)
for(int j=i+1;j<b.size();j++)
{
if(ok(b[i],b[j])) ++ans;
if(ok(b[j],b[i])) ++ans;
}
printf(“case #%d:\n%d\n”,step,ans);
}
return 0;
}
Twisted9
朴实无华
include
using namespace std;
int GCD(int a,int b)
{
return b==0?a:GCD(b,a%b);
}
int main()
{
int a,n,T;
set S;
cin >> T;
for(int i = 0;i < T;i++)
{
cin >> n;
for(int j = 0;j < n;j++)
{
cin >> a;
S.insert(a);
}
int ans = 0;
while(S.size() > 1)
{
auto p = S.begin();
int t = *p;
S.erase(p);
for(auto x : S)
{
if(GCD(x,t) == 1)
ans++;
}
}
cout << "case #" << i << ":" << endl;
cout << ans << endl;
S.clear();
}
}
speen123
思路：
1.首先使用set集合来自动位元素去重以及从小到大进行排序。
2.使用 getgcd求两个元素之间的最大公约数，若最大公约数为1则表示两者可以组成最简真分数。
3.遍历整个set元素，规则是从前往后元素进行配对。
include
include
using namespace std;
int getgcd(int a,int b){
int gcd;
int t1,t2;
t1 = a;
t2 = b;
gcd = t1 % t2;
while(gcd != 0){
t1 = t2;
t2 = gcd;
gcd = t1 % t2;
}
return t2;
}
int main()
{
int T = 0;
int n = 0;
int num = 0;
int count = 0;
set number_set;
scanf(“%d”,&T);
for(int i = 0;i < T;i++){
count = 0;
number_set.clear();
scanf(“%d”,&n);
for(int j = 0 ;j < n;j++){
scanf(“%d”,&num);
number_set.insert(num);
}
for(set<int>::iterator iter_i = number_set.begin(); iter_i != number_set.end();iter_i++){
for(set<int>::iterator iter_j = iter_i;iter_j != number_set.end();iter_j++){
if(iter_i != iter_j){
if(getgcd(*iter_i,*iter_j) == 1){
count++;
}
}
}
}
printf("case #%d:\n",i);
printf("%d\n",count);
}
return 0;
}
10175102262 LarsPendragon
这题其实就是排序去重。本来以为题目要求的最简真分数指的是化简，后来发现不对，是要求本身就是最简。于是这道题就更简单了……
附C代码：
#include <stdio.h>
#include <stdlib.h>
int gcd(int a, int b)
{
if(a%b) return gcd(b,a%b);
else return b;
}
int cmp(const void*a, const void*b)
{
int *p1=(int*)a, *p2=(int*)b;
return *p1-*p2;
}
int main()
{
int T, I;
scanf("%d",&T);
for(I=0; I<T; I++)
{
int n, i, j, x, num[1000], cnt=0;
scanf("%d",&n);
for(i=0; i<n; i++)
{
scanf("%d",&num[i]);
for(j=0; j<i; j++) if(num[j]==num[i]) {n--; i--; break;}
}
qsort(num, n, sizeof(int), cmp);
for(i=0; i<n-1; i++)
for(j=i+1; j<n; j++)
{
if(!(num[i]-num[j])) continue;
x=gcd(num[j], num[i]);
if(x==1) cnt++;
}
printf("case #%d:\n%d\n",I,cnt);
}
return 0;
}
Fifnmar
很多同学以为C++不如Python Java 等语言好写，虽然有一定正确的地方，但还有可能是没有了解C++的STL。
不久C++20就出来了，那时候C++将成为真正好写又好用的语言。
#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>
#include <vector>
using namespace std;
struct Fraction {
int numerator;
int denominator;
bool operator<(Fraction const &frac) const {
return numerator * frac.denominator < frac.numerator * denominator;
}
};
int main() {
ios::sync_with_stdio(false);
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
int n;
cin >> n;
set<Fraction> pool;
vector<int> nums(n);
for (auto &i : nums)
cin >> i;
sort(nums.begin(), nums.end());
for (int j = 0; j < n; ++j)
for (int k = j + 1; k < n; ++k)
if (gcd(nums[k], nums[j]) == 1)
pool.insert({nums[j], nums[k]});
pool.erase({1, 1});
cout << "case #" << i << ":\n" << pool.size() << '\n';
}
}
Commando
#include <bits/stdc++.h>
using namespace std;
int solve(const set<int>& s) {
int res = 0;
for (auto i = s.begin(); i != s.end(); ++i) {
for (auto j = next(i); j != s.end(); ++j) {
int m = *i, n = *j;
if (m < n && gcd(m, n) == 1) ++res;
}
}
return res;
}
int main() {
int T, N, num, n = 0;
cin >> T;
while (T--) {
cin >> N;
set<int> s;
while (N--) cin >> num, s.insert(num);
printf("case #%d:\n%d\n", n++, solve(s));
}
}
你说得很有道理
（点赞）