[CQOI2007]\u4f59\u6570\u4e4b\u548csum<\/p>\n
Time Limit:5000MS Memory Limit:165536K
Total Submit:41 Accepted:17
Case Time Limit:1000MS<\/p>\n
Description <\/strong><\/p>\n \u7ed9\u51fa\u6b63\u6574\u6570n\u548ck\uff0c\u8ba1\u7b97j(n, k)=k mod 1 + k mod 2 + k mod 3 + \u2026 + k mod n\u7684\u503c\uff0c\u5176\u4e2dk mod i\u8868\u793ak\u9664\u4ee5i\u7684\u4f59\u6570\u3002 Input <\/strong><\/p>\n \u8f93\u5165\u4ec5\u4e00\u884c\uff0c\u5305\u542b\u4e24\u4e2a\u6574\u6570n, k\u3002 <\/p>\n Output <\/strong><\/p>\n \u8f93\u51fa\u4ec5\u4e00\u884c\uff0c\u5373j(n, k)\u3002 <\/p>\n Sample Input <\/strong><\/p>\n<\/p>\n Sample Output <\/strong><\/p>\n<\/p>\n Hint <\/strong><\/p>\n 50%\u7684\u6570\u636e\u6ee1\u8db3\uff1a1<=n, k<=1000 Source #include <iostream>using namespace std;typedef long long ll;int main(){ int n,k;cin>>n>>k;ll ans=0; for(int i=1;i<=n;i++) { int a=k\/i,l=k\/(a+1)+1,r=a?k\/a:n; if(r>=n)r=n; ans+=ll(k)*(r-l+1)-ll(a)*(l+r)*(r-l+1)\/2; i=r; } cout<<ans<<endl;}75 3 <\/p>\n","protected":false},"excerpt":{"rendered":" [CQOI2007]\u4f59\u6570\u4e4b\u548csum Time Limit:5000MS Memory Limit:165536KTotal Submit:41 Accepted:17 Case Time Limit:1000MS Description \u7ed9\u51fa\u6b63\u6574\u6570n\u548ck\uff0c\u8ba1\u7b97j(n, k)=k mod 1 + k mod 2 + k mod 3 + \u2026 + k mod n\u7684\u503c\uff0c\u5176\u4e2dk mod i\u8868\u793ak\u9664\u4ee5i\u7684\u4f59\u6570\u3002 \u4f8b\u5982j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7 Input \u8f93\u5165\u4ec5\u4e00\u884c\uff0c\u5305\u542b\u4e24\u4e2a\u6574\u6570n, k\u3002 Output […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/281"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=281"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/281\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=281"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=281"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=281"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u4f8b\u5982j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7 <\/p>\n
100%\u7684\u6570\u636e\u6ee1\u8db3\uff1a1<=n ,k<=10^9 <\/p>\n
\u989d\u3002\u3002k mod i=k-(k\/i)*i\u3002\u3002\u3002
\u90a3\u4e48\u5bf9\u4e8e\u4e00\u6bb5k\/i\u76f8\u7b49\u7684\u53ef\u4ee5\u4e00\u8d77\u8ba1\u7b97\u3002\u3002
\u53ef\u4ee5\u8bc1\u660e\u6700\u591a\u5206\u6210sqrt\uff08n\uff09\u6bb5\u3002\u3002
Code\uff1a
<\/strong><\/p>\n