ABC280D分解质因数筛法应用时间复杂度

n是long long类型，要是他的倍数，很可能超出long long范围，我们可以对他进行质因数分解，只要每个质因子都解决了就行。

#include <stdio.h>
#define N 1000005
long long n, m, i, j, k, s, a[N], c[N];
int main(){
    scanf("%lld", &n);
    for(i=2; i<=n/i; i++){
        if(n%i == 0) a[++m] = i;
        while(n%i == 0) c[m]++, n /= i;
    }//质因子a[i]出现c[i]次
    for(i=1; i<=m; i++){
        for(j=a[i]; k=j; j+=a[i]){//只能用a[i]的倍数，优先用小的
            while(k%a[i] == 0) c[i]--, k /= a[i];
            if(c[i] < 1) break;//用完能解决就行
        }
        if(j > s) s = j;//每个质因子至少乘到j，取最大值
    }
    if(n > s) s = n;//最大的质因子，质数阶乘到它
    printf("%lld\n", s);
    return 0;
}

质因数分解时间复杂度是根号n；每个质因子a[i]，至多用c[i]个数解决，第二重for循环次数之和约log次。