莫比乌斯反演

题目描述

给定一个函数$f(1), f(2), \dots, f(n)$，已知$f(n)=\sum_{d|n} g(d)$，求$g(1), g(2), \dots, g(n)$。

输入格式

第一行四个整数$n(1\leq n\leq 10^6), A, B, C(0\leq A, B, C < 2^{32})$。

为了防止输入过大，$f$用下面代码生成。

unsigned int A,B,C;
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}
int main(){
    scanf("%d%u%u%u", &n, &A, &B, &C);
    for (int i = 1; i <= n; i++)
        f[i] = rng61();
}

输出格式

为了防止输出过大，输出所有$g$中的元素转成32位无符号整型之后的异或和。

样例输入

10 1 2 3

样例输出

4289023889