https://codeforces.com/contest/1116/problem/C2
N桁の量子状態$\ket{x}$とqubit$\ket{y}$が与えられる。$\ket{y}$をオラクルqubitとして、$\ket{x}$がperiodic（ある整数$P\;(1\leq P\leq N-1)$が存在して、$\ket{x}$が周期$P$をもつ）である場合のみ$f(x)=1$となるようなオラクルを作成せよ。
$\ket{x}$がある周期$P$をもつ場合に$\ket{y}$を反転させる操作を考えます。
状態$\ket{x}$が周期$P$をもつとは、すべての$i\;(0\leq i\leq P-1)$について$x_i=x_{i+P}=\dots=x_{i+nP}=\dots$であると言い換えることができます。もしも$\ket{x}$がそのようになっているのであれば、$\ket{x}$の$i\;(0\leq i \leq N-P-1)$桁目をターゲットビットとして$i+P$桁目を制御ビットとしたCNOTゲートを前から作用させれば0桁目から$N-P-1$桁目までのqubitはすべて$\ket{0}$になるはずです（CNOT($x$,$y$)はXor演算$x\oplus y$と同値であるため）。
このようにして、各$P$について$\ket{x}$が周期$P$をもつかどうかを（新たなqubitを割り当てることなく）調べることができるので、$\ket{x}$が各周期をもつかどうかを記録するための追加qubitを用意して、それらを入力としたOR Oracleによって$\ket{y}$を変化させればよいです。
これで、この問題が解けました。
namespace Solution {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
operation CheckPeriod(x : Qubit[], a : Qubit, P : Int) : Unit{ //xが周期Pをもつとき、aを反転させる
body (...) {
let N=Length(x);
for(i in 0..N-P-1){
CNOT(x[i+P],x[i]);
}
(ControlledOnInt(0,X))(x[0..N-P-1],a);
for(i in N-P-1..-1..0){ //xを戻す
CNOT(x[i+P],x[i]);
}
}
adjoint auto;
}
operation Solve (x : Qubit[], y : Qubit) : Unit {
body (...) {
let N=Length(x);
using(a=Qubit[N-1]){ //xが周期Pをもつとき、a[P-1]=|1⟩
for(P in 1..N-1){
CheckPeriod(x,a[P-1],P);
}
(ControlledOnInt(0,X))(a,y);
X(y);
for(P in 1..N-1){ //aを戻してからリリース！
CheckPeriod(x,a[P-1],P);
}
}
}
adjoint auto;
}
}