首页 > 代码库 > lightoj 1089
lightoj 1089
很有意思的题目,1到n的所有数的约数的合。
sqrt(n)一次算两两边的。
#include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <stack> #include <cstdlib> #include <queue> #include <map> #include <iostream> #include <algorithm> #include <bits/stdc++.h> using namespace std; typedef long long LL; LL cal(LL x) { LL ans=0; for (LL i=2;i<=sqrt(x);i++) { ans+=(x/i-1)*i; LL zuo=x/(i+1),you=x/(i); if (you!=i) { ans+=(zuo+1+you)*(you-zuo)/2*(i-1); } } return ans; } //long long getAns(long long m) //{ // long long ans = 0; // for(long long i = 2;i<=sqrt(m);i++) // { // ////前sqrt(n)个约数 // ans += (m/i-1)*i; // ////约数个数为前sqrt(n) // long long j = m/i; // long long q = (m/(i+1)); // if(j!=i) // { // ans += (j+q+1)*(j-q)/2*(i-1); // } // } // return ans; //} int main() { int T,ncas=1; LL x; scanf ("%d",&T); while (T--) { scanf ("%lld",&x); printf ("Case %d: %lld\n",ncas++,cal(x)); } return 0; }
lightoj 1089
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。