[考试题] Decimal 数论

题目大意

给定正整数K, Q, 接下来Q次询问, 每次询问给定N _i 问[latex]\frac{1}{N_i}[/latex]的K进制小数表示法下最小循环节长度。
K, Q, N ≤ 2000000

解题报告

模拟除法的过程, 显然如果N的质因子K都有那么答案是0(没有循环节)。

显然答案x满足\( K^{(x+1)} \equiv K \mod N \), 推至[latex]K^x \equiv 1 \mod{N}[/latex]。

假设N和K互质, 那么根据欧拉定理可得[latex]K^{\varphi(N)} \equiv 1[/latex]。发现如果将N和K共有的素因子从N内删去不会改变答案, 于是删去就可以满足欧拉定理了。

现在x一定是[latex]\varphi(N)[/latex]的因子, 暴力枚举因子+检验即可, 复杂度[latex]O(N\sqrt{N}log_2(N))[/latex]。

然而这样只有60pts…(考试时没算复杂度, 以为一定能 O(松) 过就没管爆了..)

复杂度瓶颈在于枚举欧拉函数因子。可以筛出所有质因子, 然后从欧拉函数值x里尝试扔掉一些因子看剩下的x能否满足条件, 如果不能满足就不扔, 由于质因子数量是log级别的, 复杂度优化到[latex]O(Nlog_2^2(N))[/latex]。

进一步优化, 首先令[latex]ord_K(N)[/latex]满足[latex]K^{ord_K(N)} \equiv 1 \mod{N}[/latex]且[latex]ord_K(N)[/latex]最小, 那么有以下结论:

1.当[latex]gcd(a, b) = 1[/latex]时, [latex]ord_K(a\times b) = lcm(ord_K(a), ord_K(b))[/latex]。

2.若[latex]a|b[/latex], 那么有[latex]ord_K(a)|ord_K(b)[/latex]。

…然后发现这个很像线性筛, 就可以筛了…发现素数不能筛出ord, 于是使用一次上文提到的log级别时间的从欧拉函数里剔除因子的方法把ord暴力出来, 由于小于等于N的素数数量大约为[latex]\frac{N}{ln(N)}[/latex], 所有复杂度会少一个log, 就可以过了。

代码

常数很大, 开O2在奔腾上要跑两秒…

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const int MAXL = 2000020;
const int INF = 0x3f3f3f3f;
inline int getInt () {
    int ret; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0');
    return flg ? -ret : ret;
}
int fac[MAXL];
int prec[MAXL], ptot;
int ord[MAXL];
bool isnprime[MAXL];
int K;
inline int advPow (int a, int b, int c) {
    int ret = 1;
    while(b) {
        if(b&1) ret = (LL)ret*a%c;
        a = (LL)a*a%c;
        b >>= 1;
    }
    return ret;
}
inline int gcd (int a, int b) {
    return b ? gcd(b, a%b) : a;
}
inline int lcm (int a, int b) {return a/gcd(a, b)*b;}
void factorShaker (int N) {
    for(int i = 2; i<=N; i++) {
        //if(i%1000 == 0) puts("hello");
        if(!isnprime[i]) {
            fac[i] = i;
            prec[++ptot] = i;
            int x = i-1, t = i-1;
            while(x != 1) {
                if(advPow(K, t/fac[x], i) == 1) t/=fac[x];
                x /= fac[x];
            }
            ord[i] = t;
        }
        int t;
        for(int j = 1; j <= ptot && (t = prec[j]*i)<=N; j++) {
            isnprime[t] = true;
            fac[t] = max(fac[i], prec[j]);
            if(i%prec[j] == 0) {
                for(int k = 1; k<=prec[j]; k++)
                    if(advPow(K, ord[i]*k, t) == 1) {
                        ord[t] = ord[i]*k;
                        break;
                    }
                break;
            } else {
                ord[t] = lcm(ord[i], ord[prec[j]]);
                fac[t] = max(fac[i], prec[j]);
            }
        }
    }
}
int main () {
	freopen("decimal.in", "r", stdin);
	freopen("decimal.out", "w", stdout);
    K = getInt();
    int Q = getInt();
    factorShaker(2000010);
    int result = 0;
    for(int i = 1; i<=Q; i++) {
        int N;
        scanf("%d", &N);
        while(gcd(N, K) != 1) N /= gcd(N, K);
        if(N == 1) {result ^= i; continue ;}
        //printf("ans:%d\n", ord[N]);
        result ^= ord[N]+i;
    }
    cout << result << endl;
}