oj.uz

Submission #1088868

# Submission time Handle Problem Language Result Execution time Memory
1088868 2024-09-15T11:38:49 Z Sunbae Savrsen (COCI17_savrsen) C++17
120 / 120
 1088 ms 39516 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int s[10000001];
ll powr(ll A, int B){
	ll res = 1;
	while(B){
		if(B&1) res *= A;
		A *= A;
		B>>=1;
	}
	return res;
}
signed main(){
	int A, B; scanf("%d %d", &A, &B);
	s[1] = 1; 
	for(int i = 2; i<=B; i+=2) s[i] = 2;
	for(int i = 3; i<=B; i+=2) s[i] = i;
	for(ll i = 3; i<=B; i+=2){
		if(s[i] == i){
			for(ll j = i*i; j<=B; j+=i+i) s[j] = min(s[j], (int)i);
		} 
	}
	ll tot = 0;
	for(int i = A; i<=B; ++i){
		map<int,int> mp;
		ll pd = 1;
		for(int x = i; x > 1; x /= s[x]) mp[s[x]]++;
		for(pair<int,int> it: mp){
			pd *= (powr(it.first, it.second+1) - 1ll)/(it.first-1ll);
		}
		tot += abs(2*i - pd);
	}
	printf("%lld", tot);
}

Compilation message

savrsen.cpp: In function 'int main()':
savrsen.cpp:15:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  int A, B; scanf("%d %d", &A, &B);
      |            ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 9 ms 848 KB Output is correct
4 Correct 56 ms 39508 KB Output is correct
5 Correct 966 ms 39516 KB Output is correct
6 Correct 1088 ms 39516 KB Output is correct
7 Correct 948 ms 36444 KB Output is correct
8 Correct 246 ms 10160 KB Output is correct