SRM 487 Div2 Hard BunnyConverter

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10746&rd=14240
自然数z, nが与えられる。
xを入力として、x + y^2 + z^3 = n (mod n)となるようなyを出力する機械がある。ただしyは1からnまでの間の数で、複数ありうる場合は任意のものを出力とできる。xをstartから始めてyをgoalとするまでに必要な最短の機械の使用回数を返せ。 n <= 500,000

やりかた

Editorialを参考にしました。
goalをyに入れてxを取り出して何回でxがstartになるか調べればいい。xからyの取り出し方は複数通りあるけど、yからxの取り出し方は1通りしかない。同じxが複数回出てくるとそこから無限ループになるのでその場合は-1を返す。
なので負のmodを取らないように注意する。

以下ソース。

bool visited[500001];

class BunnyConverter {
public:
  int getMinimum(int n, int z, int start, int goal) {
    ll N = n;
    ll z3 = (ll)z * z * z % N;
    ll y = goal;
    int cnt = 0;
    memset(visited, false, sizeof(visited));
    while(y != start){
      visited[y] = true;
      ll x = ((N - (y * y) % N) % N + (N - z3) % N) % N;
      if(x == 0) x = N;
      if(visited[x]) return -1;
      else{
	cnt++;
	y = x;
      }
    }
    return cnt;
  }
};

普通にstartから始めてBFSだと思っていた。こういう発想もできるようにしたい。

kusano_progさんの解答が綺麗なのでそっちを参考にしよう（提案）