SRM 652 Div1 250 : ThePermutationGame

問題概要:
これまた備忘録なので略

解法：
１からNまでの周期が存在するので（＜＝ノートに書いてたらそんな感じ、直感的に）
１からNまでの最小公倍数を求めれば良い（＜＝さっきのことがわかればそうなるでしょうね）
１からNまでで存在する素数を列挙し、それらをNを超えない最大のべき乗をもとめる（＜＝はい、）
あとはそれらを掛け合わせる

普通に１からNまでループ回して a / __gcd(a,b) * b みたいなことしたら mod とってるおかげでうまくいかなかった
a * mod_inv(__gcd(a,b),mod) * b ともしてみたけどだめだったので上のような方法にした

コード：

const ll mod = 1000000007LL;
const int  MAX = 1000000;
bool isntprime[MAX+1]; 
vector<int> prime;

class ThePermutationGame {
public:
	
  void init(){
    isntprime[0] = isntprime[1] = true;
    int j;	
    for(int i=2;i<= MAX;i++)if(!isntprime[i])for(prime.push_back(i),j=2*i;j<=MAX;j+=i)isntprime[j] = true;
  }  

  int findMin(int N) {
    init();
    ll answer = 1;
    rep(i,prime.size()){
      if( prime[i] > N ) break;
      ll multi = prime[i];
      ll coef  = prime[i];
      while( multi*coef <= (ll)N ) multi *= coef;
      ( answer *= multi ) %= mod;
    }
    return answer;
  }
};