uva 1363 公式求和(优化)

2019-04-13 21:30发布

站内文章 / 模拟电子
15509 0 1017
点击打开链接
//计算 累加k%i (i:1~n)
//n,k<=1e9直接算超时,k固定除数增加,下取整,商相同的有很多 
//若k/i=p &&k/(i+1)=p
//则k%(i+1)=k-(i+1)*p=k-ip-p=k%i-p
//即商的整数部分相同的i~j的余数呈等差数列 
#include #include using namespace std; const int N=1e3+20; typedef long long ll; const ll mod=1e9+7; int main() { ll n,k; //计算 累加k%i (i:1~n) //n,k<=1e9直接算超时,k固定除数增加,下取整,商相同的有很多 //若k/i=p &&k/(i+1)=p //则k%(i+1)=k-(i+1)*p=k-ip-p=k%i-p //即商的整数部分相同的i~j的余数呈等差数列 while(cin>>n>>k) { int i=1; ll ans=0; while(i<=n) { ll p=k/i; ll j; if(p==0)//k

热门文章