[PRACTICE][1]
[CONTEST][2]
Author- [Medha Pandey][3]
Tester- [Akanksha Bigasia][4]
Editorialist- [Sanya Tayal][5]
DESCRIPTION
Given an integer N find the GCD for for calculating rows to arrange chocolates in N number of stocks having particular number of choclates arranged in x number of rows.
EXPLANATION :
Calculate GCD for N number of stocks for all natural numbers from 1 to N. Run a loop from 1 to N and number of rows would be sum of all possible numbers for GCD. Final answer is x .
CODE:
int gcd(int a, int b)
{
if(a % b==0) return b; //to calculate GCD
return gcd(b,a % b);
}
int div[1000001], p, exp;
long long f1[1000001],f2[1000001],aux,pow;
int main()
{
memset(div,-1,sizeof(div));
for(int i = 2;i< =1000000;++i){
if(div[i]==-1)
{
div[i] = i;
if(i< =1000)
for(int j = i * i;j< =1000000;j += i)
div[j] = i;
}
}
memset(f2,-1,sizeof(f2));
f1[1] = 0;
f2[1] = 1;
for(int i = 2;i< =1000000;++i)
{
p = div[i]; exp = 0;
aux = i; pow = 1;
while(aux%p==0)
{
pow * = p;
++exp;
aux /= p;
}
f2[i] = ((exp+1)* pow-exp* (pow/p))* f2[aux];
f1[i] = f1[i-1]+f2[i]-i;
}
int N;
while(true){
scanf("%d",&N);
if(N==0) break;
printf("%lld\n",f1[N]);
}
[1]: https://www.codechef.com/problems/CCFY
[2]: https://www.codechef.com/IC32016
[3]: https://www.codechef.com/users/mack8
[4]: https://www.codechef.com/users/akku_bigasia
[5]: https://www.codechef.com/users/stayal