HNUST OJ 1945 个位求和【增强版】

问题 L: 个位求和【增强版】
时间限制: 1 Sec  内存限制: 128 MB

题目描述
将一个整数区间内所有整数的个位相加并输出。

输入
输入2个int类型整数m和n（m<=n），m与n之间由空格隔开。

输出
将区间[m,n]内所有整数的个位相加并输出。 

样例输入
1 18

样例输出
81

提示
新年福利，温馨提示： 
1）如果用int类型数据，暴力方法只能过90%的数据。最终可能会显示”答案错误10%“或”时间超限10%“。在OI排名表中可以看出得9分。没有优化思路的，得9分后请立刻转做其它题。 
2）如果想过另外10%的数据，请优化方法，且注意如果变量或运算的数据超过int最大值（2147483647），请采用long long定义变量， 变量的scanf和printf 请使用%lld作为格式说明符。

 思路

1. 对于  我们有   为 区间  内所有整数的个位和。

 

2. 找规律 我们拿    为例

当  时 , 

当  时 , 

当  时 ,

所以规律①    当且仅当  

然后再以    为例

当  时 ,

当  时 ,

当  时 ,

可知 要在规律①上加  个数

这个数 从 (向下取整,先除再乘,不可抵消)开始

所以答案就出来了。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll Plus (int a , int b) {ll temp=0;ll t=b-a+1;ll n=t/10;ll k=(a+n*10)%10;for (int i = 0 ; i < (b-a+1)%10 ; i++) {if (k == 10) {k = 0 ;}temp += k;k++ ;}return 45*n + temp ;
}
int main(){int m,n;ll ans=0;cin >> m >> n ;if (n < 0) {ans = Plus(-n,-m) ;} else if (m < 0) {ans = Plus(0,-m) + Plus(0,n) ;} else {ans = Plus(m,n) ;}cout << ans ;return 0;
}
/**************************************************************Problem: 1945User: 21XXXXXXXXLanguage: C++Result: 正确Time:0 msMemory:2024 kb
****************************************************************/

// 这里提供一个更容易的方法，建议学习这个#include <bits/stdc++.h>
using namespace std;// 2023 OneWanlong long get(int n) { // 此函数求 0 到 n 的个位和if (n < 0) return 0LL;return 45LL * (n / 10) + (n % 10) * (n % 10 + 1) / 2;
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int m, n;cin >> m >> n;if (m > 0) cout << get(n) - get(m - 1);else if (n < 0) cout << get(-m) - get(-n - 1);else cout << get(n) + get(-m);return 0;
}
/**************************************************************Problem: 1945User: 21XXXXXXXXLanguage: C++Result: 正确Time:0 msMemory:2180 kb
****************************************************************/