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

n+e

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

 
 
 

日志

 
 

[BZOJ2693/2154]jzptab  

2015-03-16 20:16:00|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2693: jzptab

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 449  Solved: 176
[Submit][Status][Discuss]

Description

Input

一个正整数T表示数据组数

接下来T行 每行两个正整数 表示NM

Output

T行 每行一个整数 表示第i组数据的结果

Sample Input

1

4 5

Sample Output

122

HINT

T <= 10000

N, M<=10000000

Solution

[BZOJ2693/2154]jzptab - Trinkle - n+e
 

Code

/**************************************************************
    Problem: 2693
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:4916 ms
    Memory:127840 kb
****************************************************************/
 
#include<cstdio>
#define N 10000010
#define p 100000009
int _,t,pr[N],n,m,a[10010],b[10010],i,j,l,r,t0,t1;long long ans,g[N];bool vis[N];
int aa;char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
long long S(long long n,long long m){
    return 75000007LL*n%p*m%p*(n+1)%p*(m+1)%p;
}
void work(int n,int m){
    for(ans=0,l=1;l<=n;l=r+1){
        t0=n/l,t1=m/l,r=n/t0<m/t1?n/t0:m/t1;
        ans=(ans+S(t0,t1)*(p+g[r]-g[l-1])%p)%p;
    }
}
int main(){
    for(_=F(),i=1;i<=_;i++)a[i]=F(),b[i]=F(),
    a[i]>b[i]?j=a[i],a[i]=b[i],b[i]=j:1,n<b[i]?n=b[i]:1;
    for(g[1]=1,i=2;i<=n;i++){
        if(!vis[i])pr[++t]=i,g[i]=1LL*i*(p+1-i)%p;
        for(j=1,m=n/i;j<=t&&pr[j]<=m;j++){
            vis[pr[j]*i]=1;
            if(i%pr[j]==0){
                g[i*pr[j]]=1LL*pr[j]*g[i]%p;break;
            }
            g[i*pr[j]]=1LL*g[pr[j]]*g[i]%p;
        }
    }
    for(i=2;i<=n;i++)g[i]=(p+g[i]+g[i-1])%p;
    for(i=1;i<=_;i++)work(a[i],b[i]),printf("%lld\n",ans);
}

  评论这张
 
阅读(93)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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