Cod sursa(job #2577101)

Utilizator 1chiriacOctavian Neculau 1chiriac Data 8 martie 2020 14:02:47
Problema Fractii Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;
int n,v[100005],s,kontor,p;bitset <1000007> prime;
int putere (int a, int b) {
	p=1;
	for(int i=0;b>0;++i) {
		if((b & (1<<i))!=0) 
			b^=(1<<i),p*=a;
		a=a*a;
	}
	return p;
}
int fi (int nr) {
	s=1;
	for(int i=1;nr>1;++i) {
		if(nr%v[i]==0) {
			kontor=0;
			while(nr%v[i]==0)
				++kontor,nr/=v[i];
			s=s*(v[i]-1)*putere(v[i],kontor-1);
		}
	}
	return s;
}
int main () {
	long long ans=1;
	freopen("fractii.in","r",stdin);
	freopen("fractii.out","w",stdout);
	scanf("%d", &n);prime[0]=1;prime[1]=1;
	for(int i=2;i<=n;++i)
		if(prime[i]==0) {
			v[++v[0]]=i;
			for(int j=2;i*j<=n;++j)
				prime[i*j]=1;
		}
	for(int i=2;i<=n;++i) 
		ans=ans+2LL*(long long)fi(i);
	printf("%lld", ans);
	return 0;
}