首页 > 代码库 > BZOJ3560: DZY Loves Math V

BZOJ3560: DZY Loves Math V

2024-08-05 05:35:52   216人阅读

虽然不是很神的题，不过拿短代码搞到rank1了那么纪念下。

先观察样例。

6=2*3;

10=2*5;

15=3*5;

对应答案：1595=5*11*29；

其中：

5=（（1+2）*（1+2）*1*（2-1）+1）/2

11=（（1+3）*1*（1+3）*（3-1）+1）/3

29=（1*（1+5）*（1+5）*（5-1）+1）/5

 

证明不写了……自行领会精神。

就是对每个n因数分解后对每个p分开搞搞。

 

【代码】（话说好不容易才发现插入代码这功能）
 1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstring> 5 using namespace std; 6 #define rep(i,j,n) for(int i=j;i<=n;i++) 7 char c;template<class T> inline void read(T&x){for(c=getchar();c<‘0‘||c>‘9‘;c=getchar());for(x=0;c>=‘0‘&&c<=‘9‘;c=getchar())x=x*10+c-‘0‘;}; 8 const int N=10000000,M=664580,mod=1000000007; 9 int ta,tb,n,x,phi[N+1],p[M];10 long long tc,td,d[M];11 bool pd[N+1];12 void pre(){13     pd[1]=1;14     rep(i,2,N){15         if(!pd[i])p[++p[0]]=i,phi[i]=p[0];16         for(int j=1,mul;j<=p[0]&&(mul=i*p[j])<=N;j++){17             pd[mul]=1;phi[mul]=j;18             if(i%p[j]==0)break;19         }20     }21     rep(i,1,p[0]) d[i]=1;22     memset(pd,false,sizeof(pd));23 }24 int main(){25     pre();26     read(n);27     rep(i,1,n){28         read(x);29         while(x>1){30             ta=phi[x];tb=1;tc=1;31             while(x%p[ta]==0){32                 tc=tc*p[ta]%mod;33                 tb=tb+tc;34                 if(tb>=mod)tb-=mod;35                 x/=p[ta];36             }37             d[ta]=d[ta]*tb%mod;38             pd[ta]=true;39         }40     }41     tc=1;td=1;42     rep(i,1,p[0]) if(pd[i]){43         tc=tc*(d[i]*(p[i]-1)%mod+1)%mod;44         td=td*p[i]%mod;45     }46     ta=mod-2;47     while(ta){48         if(1&ta) tc=tc*td%mod;49         td=td*td%mod;50         ta>>=1;51     }52     printf("%lld\n",tc);53 }

 

 

BZOJ3560: DZY Loves Math V


联系
我们