SRM617 div1 easy MyLongCake

概要

長さnのケーキがあり友人に配るためケーキを切っておきたい。友人には同じ長さの連続したピースのケーキを渡せるようにしたい。来る友人の人数はn以外のnの約数の人数ということしかわかっていない。この条件を満たすような最小のピースの数を出力しろ。

解法

a人来るときは{n/a, 2n/a, 3n/a, …, (a-1)*n/a}の位置を切るしかない。 約数の列挙はO(sqrt(n))でできるので解ける。

#include <bits/stdc++.h>
using namespace std;

class MyLongCake {
   public:
   int cut(int n)
  {
    set<int> st;
    for(int i=2; i*i<=n; ++i) {
      if(n%i==0) {
        for(int j=n/i; j<n; j+=n/i) st.insert(j);
        for(int j=i; j<n; j+=i) st.insert(j);
      }
    }
    return st.size()+1;
  }
};