Topcoder SRM 535(Div.2) 参戦記

狐と鰻の仲の良さがわかる回です。

250-Problem:連立方程式の問題です。対称式なので、足したり引いたりすれば答えがでます。3つの未知数に対して4つの式がありますから、そこだけ注意しました。久しぶりなので、カンを取り戻しつつ丁寧に回答して、208.97pts.

500-Problem: m*n=GCD(m,n)*LCM(m,n)の関係を使います。これと、ユークリッドの互除法、Lの約数の全探索で書けばOKでした。しかし、Lの約数のうち、Gの倍数であるもののリストを取得して確認していったほうが手早いかもしれません。284.88pts.

問題はこちら(英語).
得点は493.85, 順位は81/1412. Ratingは1125->1200. ついに青くなりました。次からはDiv.1ですので、少し心配です。

[Easy(C++),Accepted]

#include<cstdio>
#include<iostream>
#include<vector>


using namespace std;


class FoxAndIntegers{
public:
vector <int> get(int AminusB, int BminusC, int AplusB, int BplusC){
vector<int> ret(3);
vector<int> empty(0);
if((AplusB + AminusB)%2!=0) return empty;
if((BplusC - BminusC)%2!=0) return empty;
if((AplusB - AminusB)%2!=0) return empty;
if((AplusB - AminusB)!=(BplusC + BminusC)) return empty; 
ret[0]=(AplusB + AminusB)/2;
ret[1]=(AplusB - AminusB)/2;
ret[2]=(BplusC - BminusC)/2;
return ret;
}
};

[Medium(C++),Accepted]


#include<iostream>
#include<cmath>


using namespace std;


class FoxAndGCDLCM{
public:
long long get(long long G, long long L){
long long sum=-1,tmp;
for(long long i=1;i*i<=L;i++){
if(L%i!=0) continue;
tmp=L/i*G+i;
if(euclid(i,tmp-i)==G && (sum>tmp || sum==-1)) sum=tmp;
long long k=L/i;
tmp=L/k*G+k;
if(euclid(k,tmp-k)==G && (sum>tmp || sum==-1) ) sum=tmp;
}
return sum;
}

long long euclid(long long a,long long b){
if(b==0) return a;
return euclid(b,a%b);
}
};