読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

循環少数のプログラム

フロイドの循環検出法 - Wikipedia
これを使うらしい

int f(int n)
{
  int p = 1, q = 1;
  int s = 0, t = 0; // start : s, goal : t
  while(1)
  {
    p = (p*10)%n;
    q = (q*10)%n;
    q = (q*10)%n;
    if(p==q) break;
  }
  if(p!=0)
  {
    q = 1;
    s = 1;
    while(p!=q)
    {
      s++;
      p = (p*10)%n;
      q = (q*10)%n;
    }
    q = (q*10)%n;
    t = s;
    while(p!=q)
    {
      t++;
      q = (q*10)%n;
    }
  }
  return t-s+1;
}