题解 UVA12619 【Just Make A Wish】

· · 题解

观察题目范围，显而易见不能暴力做。（高精 python 党此句作废）

肉眼可见，矩形的个数就是因子的个数。

考虑打表，打出 10^6 以内的质数，以及 fst_i 表示 i 的第一个质因子。

\tt{Code:} 
for(register ll i=0;i<=1000000;i++){
    fst[i]=i;
}
for(register ll i=2;i*i<=1000000;i++){
    if(die[i]==false){
        for(register ll j=i;i*j<=1000000;j++){
            die[i*j]=true;
            if(fst[i*j]==i*j){
                fst[i*j]=i;
            }
        }
    }
}

令当前数的因子数量为 now，维护一个 some_i 表示 now 中有多少个因子 i。

令现在更新的值为 opt。考虑枚举 opt 的所有因子。

怎么枚举呢？

我有 fst！

考虑对 opt，不断取 fst_{opt}，然后更新 some_{fst_{opt}} 即可。

另外，还要更新 now，首先把 fst_{opt} 除掉，然后更新 num，最后再重新拿回来。

注意要取模，所以记得套上逆元！

\tt{Code}: 
scanf("%lld",&day);now=0;sum=1;
memset(some,0,sizeof(some));
for(register ll i=1;i<=day;i++){
    scanf("%lld",&opt);flag=1;
    if(opt<0){
        flag=-1;opt=-opt;
    }
    while(opt>1){
        sum*=find_inv(some[fst[opt]]+1);sum%=mod;
        some[fst[opt]]+=flag;
        sum*=some[fst[opt]]+1;sum%=mod;
        opt/=fst[opt];
    }
    now+=sum;now%=mod;
}
printf("Case %lld: %lld\n",c,now);

AC 记录图好像很糊：

祝大家 \color{black}\rm{AC} 愉快！