 # CCFY - EDITORIAL

[PRACTICE]

[CONTEST]

Author- [Medha Pandey]

Tester- [Akanksha Bigasia]

Editorialist- [Sanya Tayal]

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, p, exp;
long long f1,f2,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 = 0;
f2 = 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]);
}

: https://www.codechef.com/problems/CCFY
: https://www.codechef.com/IC32016
: https://www.codechef.com/users/mack8
: https://www.codechef.com/users/akku_bigasia
: https://www.codechef.com/users/stayal``````
//