ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 2048 Everlasting...?

問題文はこちら↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2048


・概要
ストーリー性のある問題ですが、やることは以下の通りです。
整数a,bが与えられる(2 <= a,b <= 10^6)
各整数に対し、最大の素因数からそれ以外の素因数の和を引いた値を計算する。
その値の大小を比較しaまたはbを出力する。
といった問題です。


・解法
やるだけです。

10^6までの素数表をまず先に作っておきます。
与えれたa,bに対して、最大の素因数(largest)とそれ以外の素因数の和(sum)を計算し、比較をすればOKです。


ソースコード

#include<iostream>
#include<cmath>
#include<vector>
#define MAX 1000000
using namespace std;

vector<int> prime;
bool flag[MAX+1];

void eratos(int N){
   for(int i = 0 ; i <= N ; i++)flag[i] = false;
   for(int i = 3 ; i <= N ; i+=2)flag[i] = true;
   prime.push_back(2);
   flag[2]=true;
   
   for(int i = 3 ; i <= N ; i += 2){
      if(!flag[i])continue;
      prime.push_back(i);
      for(int j = i + i ; j <= N ; j+=i)flag[j]=false;
   }
}

int calc(int v){
   int largest = 0;
   int sum = 0;

   for(int i = 0 ; i < prime.size() ; i++){
      if(v < prime[i])break;

      bool update = false;
      while(v%prime[i]==0){
	 update = true;
	 v/=prime[i];
	 largest = prime[i];
      }

      if(update)sum+=largest;
   }

   return 2*largest - sum;
}

int main(){
   eratos(MAX);
   int a,b;

   while(cin >> a >> b){
      if(a==0 && b==0)break;

      cout << (calc(a) > calc(b) ? "a" : "b") << endl;
   }
   return 0;
}