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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2956]模积和  

2015-01-29 18:24:01|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2956: 模积和

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 660  Solved: 297
[Submit][Status]

Description

 求∑∑((n mod i)*(m mod j))其中1<=i<=n,1<=j<=m,i≠j。

  

Input

第一行两个数n,m。

Output

一个整数表示答案mod 19940417的值

Sample Input

3 4

Sample Output

1

HINT

样例说明
  答案为(3 mod 1)*(4 mod 2)+(3 mod 1) * (4 mod 3)+(3 mod 1) * (4 mod 4) + (3 mod 2) * (4 mod 1) + (3 mod 2) * (4 mod 3) + (3 mo
d 2) * (4 mod 4) + (3 mod 3) * (4 mod 1) + (3 mod 3) * (4 mod 2) + (3 mod 3) * (4 mod 4) = 1
数据规模和约定
  对于100%的数据n,m<=10^9。

Source

中国国家队清华集训 2012-2013 第一天

Solution

[BZOJ2956]模积和 - Trinkle - n+e

Code

/**************************************************************
    Problem: 2956
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:152 ms
    Memory:808 kb
****************************************************************/
 
#include<cstdio>
#define p 19940417
#define ll long long
int n,m,l,r,t0,t1;ll ans,s1n,f;
ll c1(int x){return (1LL*x*(x+1)/2)%p;}
ll c2(int x){return 3323403LL*x%p*(x+1)%p*(2*x+1)%p;}
ll s1(int n,int m){
    for(f=0,l=1;l<=m;l=r+1)
    r=n/(n/l),r>m?r=m:1,f=(f+(c1(r)-c1(l-1))*(n/l)%p)%p;
    return f;
}
int main(){
    scanf("%d%d",&n,&m);if(n>m)l=n,n=m,m=l;
    s1n=s1(n,n);ans=((1LL*n*n%p-s1n)%p)*((1LL*m*m%p-s1(m,m))%p)%p;
    f=1LL*n*n%p*m%p-1LL*m%p*s1n%p-1LL*n%p*s1(m,n)%p;
    for(l=1;l<=n;l=r+1)
    t0=n/l,t1=m/l,r=n/t0<m/t1?n/t0:m/t1,r>n?r=n:1,f=(f+(c2(r)-c2(l-1))*t0%p*t1%p)%p;
    ans=(ans-f)%p;ans%=p,ans<0?ans+=p:1;printf("%lld\n",ans);
}
  评论这张
 
阅读(29)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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