注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2956][清华集训2012-2013]模积和  

2015-01-29 14:59:15|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2956: 模积和

看似简单的地方反而比较难搞- -|
写完了各种忘记开long long
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MOD = 19940417;
const int N = 1E5+10;
const int inv6 = 3323403;
int solve1(int n){
int re=(ll)n*n%MOD,i,last = 0;
for(i=1;i<=n;i++){
last = i;
i = n/(n/i);i = min(i,n);
//printf("%d %d\n",last,i);
re = (re - (ll)(i - last+1)*(i+last)/2%MOD*(n/i))%MOD;
}//printf("\n");
return re;//+=MOD
}
//(n%i)*(m%i) = n*m - [n/i]*i*m - n*[m/i]*i + [n/i]*[m/i]*i*i
/*************
[l,r]i^2
+ (1^2 + ... + r^2)
- (1^2 + ... + (l-1)^2)
=
+ r*(r+1)/2%MOD * ((2*r+1)/3)%MOD
- ....
*************/
int solve2(int n,int m){
int i,j,k,re=((ll)n*m%MOD*n)%MOD,last,to,len,tmp[2],ni,mj,nm=((ll)n*m)%MOD;
for(k=1;k<=n&&k<=m;k++){
last = k;
i = n/(n/k);i=min(i,n);
j = m/(m/k);j=min(j,m);
k = to = min(i,j);
//printf("%d %d\n",last,to);
ni = n/i;mj = m/j;
len = (to - last +1);
tmp[0] = (ll)(last + to)*(to - last+1)/2%MOD;
tmp[1] = (ll)to*(to+1)%MOD*(2*to+1)%MOD*inv6%MOD;
if(last-1 > 0)
tmp[1] = (tmp[1] - (ll)(last-1)*(last)%MOD*(2*(last-1)+1)%MOD*inv6)%MOD;
re = (re - ((ll)m*ni + (ll)n*mj)%MOD*tmp[0] + ((ll)ni*mj%MOD*tmp[1]))%MOD;
}
return re;
}
int main(){
int i,j,t[3],n,m,ans;
scanf("%d%d",&n,&m);
if(n > m)swap(n,m);//n < m
t[0] = solve1(n);
t[1] = solve1(m);
//printf("%d %d\n",t[0],t[1]);
t[2] = solve2(n,m);
ans = ((ll)t[0]*t[1] - t[2])%MOD;
if(ans < 0)ans += MOD;
printf("%d\n",ans);
return 0;
}

题解:
∑∑((n mod i)*(m mod j))其中1in,1jm,i≠j
可以转化成(Σn%i)*(Σm%i) - (Σ(n%i)(m%i)  (i≤n&&i≤m))
前面的部分分别求n和m的部分,考虑补集转化n%i = n*n - [n/i]*i
然后因为[n/i]只有√n种取值,所以枚举一下,相同部分的i可以用等差数列求和公式
后面的部分我一开以为随便搞搞就行,结果发现反而难搞……
和前面相同,考虑补集转化,然后随便列下式子,化简后得到:
(n%i)*(m%i) = n*m - [n/i]*i*m - n*[m/i]*i + [n/i]*[m/i]*i*i
搞法和第一部分差不多,区别是这里需要平方和公式: n*(n+1)*(2*n+1)/6
有除法……直接搞就爆longlong了
暴力一下发现模数不是质数,但是和6互质,所以暴力出6的逆元,直接乘就好
其实不互质也可以搞,但是需要分类讨论比较蛋疼……
  评论这张
 
阅读(57)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017