Solutions of Sum of divisors

Select solution language

phphongyd Created at 25 likes

Hiểu bài toán: -Nếu làm theo cách thông thường chạy từ 1->n theo cách thông thường thì độ phức tạp là O(n) mà n = 1e12 nên quá thời gian ==>Chúng ta cần làm theo cách chạy đến sqrt(n) như sau: Chạy for(1->sqrt(n)): + Nếu n%i==0 thì chúng ta cộng cho i và n/i(cộng cho n/i là số ngược lại cũng là ước của n) Vd:n = 5 thì i chạy đến 2 --> chỉ có n%1==0 nên tổng các ước là i+n/i=1+5=6; + Nếu n%i!=0 thì tăng i lên xong duyệt tiếp Ra ngoài nếu mà n là số chính phương thì chúng ta phải trừ đi sqrt(n) vì khi n là scp thì i và n/i được tính 2 lần Code C++: ``` #include <bits/stdc++.h> using namespace std; long long n; int main() { cin>>n; long long d=0; long long k=sqrt(n); for(int i=1;i<=k;i++){ if(n%i==0){ d+=i+n/i; } }if(k*k==n)d-=k; cout<<d; return 0; } ```