We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This is my Java solution. And I think the difficulty should be Medium by the way.
importjava.io.*;importjava.util.*;importjava.math.BigInteger;publicclassSolution{privatestaticlongmodulo=1000_000_000+7;privatestaticBigIntegermodInt=newBigInteger(modulo+"");publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);intt=in.nextInt();while(t-->0){longN=in.nextLong();if(1L==N)System.out.println(N);elsebar(N);}in.close();}privatestaticvoiduseBigInteger(longn){n/=2;BigIntegerk1=newBigInteger(n+"");BigIntegerk2=newBigInteger((n+1)+"");BigIntegerk3=newBigInteger((8)+"");BigIntegerk4=newBigInteger((2*n+1)+"");longm=k1.multiply(k2).multiply(k3).multiply(k4).divide(newBigInteger(3+"")).mod(modInt).intValue();// System.out.println(m);longq=k1.multiply(k2).multiply(newBigInteger(2+"")).mod(modInt).intValue();// System.out.println(q);longc=k1.multiply(newBigInteger(4+"")).mod(modInt).longValue();// System.out.println("c=" + c);longd=1;longbig=(m+q+c+d)%modulo;System.out.println(big);}/** * d1 = (2n + 1) ^2 Hence d1 = 4n^2 + 4n + 1 * The numbers along the other * diagonals are simply derived from d1 by subtracting certain values. * d2 = d1 - 2n Hence d2 = 4n^2 + 2n + 1 * d3 = d2 - 2n Hence d3 = 4n^2 + 1 * d4 = d3 - 2n Hence d4 = 4n^2 - 2n + 1 * Now, all that the problem asks us to do is to sum up * the numbers d1, d2, d3, d4 for n = 1, 2, 3, . . . . .. . .. * sum = summation of (16n^2 + 4n + 4) for n = 1, 2, 3, . . . . . * Now sum up remaining things like * 16 * summation of n^2 = 8 * n * (n+1) * (2 * n + 1) / 3 * 4 * summation of n = 2 * (n) * (n+1) * summation of 4 = 4 * n * * @param n * @return */privatestaticintbar(longn){// System.out.println(n + "----------------");n/=2;//first step: calculate the summation// long sum = (long) (1+8*n*(n+1)*(2*n+1)/3+2*(n)*(n+1)+4*n);// long partA = 8*n*(n+1)*(2*n+1)/3;// long partB = 2*(n)*(n+1);// long partC = 4*n;// long partD = 1;//second step: calculate the remainderlong[]numbers=newlong[]{n,n+1,2*n+1};replaceDividible(numbers);longa=inverseModulo(modulo,8,numbers);// System.out.println("a=" + a);numbers=newlong[]{n,n+1};longb=inverseModulo(modulo,2,numbers);// System.out.println("b=" + b);numbers=newlong[]{n};longc=inverseModulo(modulo,4,numbers);// System.out.println("c=" + c);longd=1;// System.out.println("(int) ((a + b + c + d) % modulo)=" + (int) ((a + b + c + d) % modulo));longraw=(a+b+c+d)%modulo;System.out.println(raw);return0;}/** * replace the value of the number that is divisible by 3 * @param a */privatestaticvoidreplaceDividible(long[]a){for(inti=0;i<a.length;i++){if(a[i]%3==0L){a[i]/=3;}}}privatestaticintinverseModulo(longmodulo,longbase,long[]numbers){base=base%modulo;//reduce to be below integer typefor(inti=0;i<numbers.length;i++){numbers[i]%=modulo;}for(longi:numbers){base=(base*i)%modulo;}return(int)base;}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #28: Number spiral diagonals
You are viewing a single comment's thread. Return to all comments →
This is my Java solution. And I think the difficulty should be Medium by the way.