BZOJ2154: Crash的数字表格
2024-10-20 01:38:53
题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2154
题意&&题解:http://www.cnblogs.com/jianglangcaijin/archive/2013/11/27/3446169.html
我只是来发泄的!!!怎么每次打数论题都会被爆int,爆long long这种问题纠缠好久!!!!!!!!!!
我还以为这题是双倍经验呢
代码:
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #include<vector> #include<map> #include<set> #include<queue> #include<string> #define inf 1000000000 #define maxn 10000000+5 #define eps 1e-10 #define ll long long #define pa pair<int,int> #define for0(i,n) for(int i=0;i<=(n);i++) #define for1(i,n) for(int i=1;i<=(n);i++) #define for2(i,x,y) for(int i=(x);i<=(y);i++) #define for3(i,x,y) for(int i=(x);i>=(y);i--) #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go) #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
#define mod 20101009 using namespace std; inline int read() { int x=,f=;char ch=getchar(); while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();} while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();} return x*f; }
int p[maxn],tot,mu[maxn];
bool v[maxn];
void get(int m)
{
mu[]=;
for2(i,,m)
{
if(!v[i])p[++tot]=i,mu[i]=-;
for1(j,tot)
{
int k=i*p[j];
if(k>m)break;
v[k]=;
if(i%p[j])mu[k]=-mu[i];
else {mu[k]=;break;}
}
}
for1(i,m)mu[i]=((ll)mu[i]*i%mod*i%mod+mu[i-])%mod;
}
inline int sum(int n,int m)
{
return ((ll)n*(n+)/%mod)*((ll)m*(m+)/%mod)%mod;
}
inline int f(int n,int m)
{
int ret=;
if(n>m)swap(n,m);
for(int i=,j;i<=n;i=j+)
{
j=min(n/(n/i),m/(m/i));
ret=(ret+(ll)(mu[j]-mu[i-])*sum(n/i,m/i)%mod)%mod;
}
return ret;
} int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
int n=read(),m=read(),ans=;get(m);
if(n>m)swap(n,m);
for(int i=,j;i<=n;i=j+)
{
j=min(n/(n/i),m/(m/i));
ans=(ans+(ll)(i+j)*(j-i+)/%mod*f(n/i,m/i)%mod)%mod;
}
printf("%d\n",(ans+mod)%mod); return ; }
最新文章
- 《写给大忙人看的java se 8》笔记
- 一种利用 Cumulative Penalty 训练 L1 正则 Log-linear 模型的随机梯度下降法
- flash 自定义右键功能
- Poj(2253),Dijkstra松弛条件的变形
- Codeforces Round #123 (Div. 2)
- SqlDataReader对象的NextResult方法读取存储过程多个结果集
- bzoj 3637: Query on a tree VI 树链剖分 &;&; AC600
- [技术翻译] 构建现代化的Objective-C (下)
- Makefile与shell脚本的区别
- simhash--文本排重
- 《Mathematical Olympiad——组合数学》——操作和游戏
- ng-cli
- 基于visual Studio2013解决C语言竞赛题之0610冒泡排序函数
- [6278009]使用Visual Stuido Code 编写Markdown
- Spring WebFlux开门迎客,却来了一位特殊客人
- 微信小程序 Request faild 请求后台失败
- vue路由守卫(全局守卫)
- idea properties文件中文无法正常显示
- 微信公共号:CTO技术总监
- _tkinter.TclError: image ";pyimage1"; doesn&#39;t exist 解决办法