首页 > 代码库 > BZOJ 1257 [CQOI2007]余数之和sum ——Dirichlet积
BZOJ 1257 [CQOI2007]余数之和sum ——Dirichlet积
【题目分析】
卷积很好玩啊。
【代码】
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <map> #include <set> #include <queue> #include <string> #include <iostream> #include <algorithm> using namespace std; #define maxn 500005 #define ll long long #define inf 0x3f3f3f3f #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) void Finout() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("wa.txt","w",stdout); #endif } int Getint() { int x=0,f=1; char ch=getchar(); while (ch<‘0‘||ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();} while (ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f; } int n,k,r,l; ll ans=0; int main() { Finout(); n=Getint(); k=Getint(); ans=(ll)n*(ll)k; // cout<<"ans is "<<ans<<endl; int now=1; r=min(n,k); while (r) { now=k/r; // cout<<now<<" "<<n<<" "<<k<<" "<<r<<endl; l=k/(now+1)+1; // cout<<"now "<<now<<endl; // cout<<l<<"---"<<r<<endl; ans-=((ll)r+(ll)l)*((ll)r-(ll)l+1)/2LL*(ll)now; // cout<<"ans is "<<ans<<endl; r=l-1; // cout<<"r is "<<r<<endl; } cout<<ans<<endl; }
BZOJ 1257 [CQOI2007]余数之和sum ——Dirichlet积
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。