Участник:Anirogozina/Not So Flat After All

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ANARC09C/

#include <iostream>
#include<cmath>
#include<unordered_map>
#include<vector>
 
std::unordered_map<int, int> getDividers(int number){
  std::unordered_map<int, int> result;
  int copy = number;
  for (int probe = 2; probe <= number; ++probe){
    if (copy % probe == 0){
      int pow_ = 1;
      copy = copy / probe;
      while (copy % probe == 0){
        copy = copy / probe;
        pow_++;
      }
      result.insert(std::make_pair(probe, pow_));
      if (copy == 1){
        break;
      }
    }
  }
  return result;
}
 
int main() {
  std::vector<int> distances;
  std::vector<int> ordinals;
  int lhs, rhs, dist, ordinal;
  while(true){
    std::cin >> lhs;
    std::cin >> rhs;
    if (lhs == 0 && rhs == 0){
      break;
    }
    auto result_lhs = getDividers(lhs);
    auto result_rhs = getDividers(rhs);
    dist = 0;
    ordinal = 0;
    for (auto& pair: result_lhs){
      ordinal++;
      auto num = pair.first;
      auto pow_ = pair.second;
      if (result_rhs.find(num) != result_rhs.end()){
        dist += std::abs(result_rhs.at(num) - pow_);
      }else{
        dist += pow_;
      }
    }
    for (auto& pair: result_rhs){
      if (result_lhs.find(pair.first) == result_lhs.end()){
          ordinal++;
          dist += pair.second;
      }
    }
    distances.push_back(dist);
    ordinals.push_back(ordinal);
  }
  for (size_t i = 0; i < distances.size(); ++i){
    std::cout<< i + 1 <<". "<<ordinals.at(i) << ":" << distances.at(i) <<std::endl;
  }
  return 0;
}