0.Luffy và ước số

Submit solution
Points: 2 (partial)
Time limit: 1.0s
Memory limit: 10M
Author:
themiscscvn
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Luffy rất yêu thích các con số. Hôm nay anh ấy gặp một bài toàn khó và muốn nhờ bạn giúp đỡ.

Bài toán cụ thể như sau:

Gọi Gx là tổng tất cả các ước lẻ của x.

Yêu cầu tính: Ga+Ga+1+...+Gb−1+Gb với a, b cho trước.

Input:

Dòng đầu chứa số nguyên T là số lượng bộ test.

Mỗi dòng tiếp theo chứa 2 số nguyên a, b.

• 1≤T≤1000

• 1≤a≤b≤105

Output:

Với mỗi test, in ra tổng được yêu cầu trên một dòng.

Example:

Input:

Copy
3
2 4
2 5
2 6

Output:

Copy
6
12
16

Comments


  • 0
    lethanhcong2005  commented on July 30, 2024, 4:04 p.m.

    include<iostream>

    Copy
    #include<cmath>
using namespace std;
long long a[100005];
long long sumgcd(int x)
{
    long long cnt = 0;
    for(int j = 1; j * j <= x; j ++)
    {
        if(x % j == 0)
        {
            if((x/j) % 2 == 1 && j * j != x) cnt += x/j;
            if(j % 2) cnt += j;
        }
    }
    return cnt;
}
void kt()
{
    for(int i = 1; i <= 100004; i ++)
    {
        a[i] = (a[i - 1] + sumgcd(i));  
    }
}
int main()
{
    int n;
    cin>>n;
    kt();
    while(n--)
    {
        int x,y;
        cin>>x>>y;
        if(x > y) swap(x,y);
        cout<< a[y] - a[x - 1]<<endl;

    }
    return 0;
}

    dùng prefix sum array


  • 0
    MinhDuc_CNTT1_K64  commented on Oct. 31, 2023, 1:29 p.m.

    :v, tính chạy python mà giới hạn có mỗi 10MB ._.


  • 0
    nguien_24  commented on Oct. 22, 2023, 7:52 a.m. ← edit 2

    include <stdio.h>

    Copy
    int G(int x){
    int s=0;
    for (int i=1;i<=x;i+=2){
        if (x%i ==0) s +=i;
    }
    return s;
}
int main(){
    int n,a,b,s=0;
    scanf("%d\n",&n);
    int T[n];
    for (int i=0;i<=n-1;i++){
        T[i]=0;
    }
    while (n>0){
        scanf("%d %d",&a,&b);
        for (int i=a;i<=b;i++){
           T[s] = T[s] + G(i);
        }
        s++;
        n--;
    }
    for (int i=0;i<=s-1;i++){
        printf("%d\n",T[i]);
    }
}
Quá thời gian đúng đc 3 test cuối, ai cứu

  • 0
    minyoongi  commented on Oct. 1, 2020, 10:39 a.m.

    ai cứu bài này với ạ


  • 0
    minyoongi  commented on Oct. 1, 2020, 10:32 a.m. ← edited
    Copy
    #include<bits/stdc++.h>
using namespace std;
int uoc(long int n)
{
    long int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(n%i==0 && i%2==1)
        sum+=i;
    }   
    return sum;
}
int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);
   cout.tie(NULL);
   int n;
   long int x,y;
   cin>>n;
   while(n--)
   {
    cin>>x>>y;
    long int sum=0;
    for(int i=x;i<=y;i++)
    {
        sum+=uoc(i);

    }
    cout<<sum<<"\n";
   }
}

  • 0
    vu_van_phong  commented on March 8, 2018, 9:44 a.m.

    luffy thích thịt nhất thầy ạ nên thay vì những con số thya thế nó bằng miếng thịt thì hay hơn