ENCDEC04 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest Link

Author: Anjali Jha
Tester: Sunita Sen

DIFFICULTY:

EASY

PREREQUISITES:

None

PROBLEM:

2 integers X and Y are given. The last digit of all the integers in the range 1 to X(both inclusive) divisible by Y are to be summed up and printed.

EXPLANATION:

Since the size of the integers is very big, using a loop will result in a TLE. If we observe, we need only the last digits of the first 10 multiples of Y because after that, the last digits are repeated in a cycle.
So take an array and store the last digits of the first 10 multiples of Y and store then sum of all the digits in variable sum. Divide n by m and store the quotient in variable x. Calculate the number of times full cycles of 10 for Y have passed and multiply it with sum. Run a loop in the array to add the remaining last digits of multiples of Y to the final answer, which could not complete a full cycle.

TIME COMPLEXITY:

The time complexity will be O(1)

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
#define pb(x) push_back(x)
#define ll long long
#define all(v) v.begin(),v.end()
using namespace std;

void solve() {
    ll n,m,i,x,y,ans=0,sum=0;
    cin>>n>>m;
    vector<int> a(10);
    for(i=0;i<10;i++) {
        a[i]=((i+1)*m)%10;
        sum+=a[i];
    }
    x=n/m;
    y=x/10;
    ans+=sum*y;
    y=x-(10*y);
    for(i=0;i<y;i++)
        ans+=a[i];
    cout<<ans<<endl;
}
int main(){
    ios ::sync_with_stdio(0);
        cin.tie(NULL);
        cout.tie(NULL);
        int t=1;
        cin>>t;
        while(t--) {
	        solve();
        }
    return 0;
}
2 Likes