fork download
copy 
  1. package main
  2.  
  3. import (
  4.   "os"	
  5.   "bufio"
  6.   "fmt"
  7. )
  8.  
  9. var reader *bufio.Reader = bufio.NewReader(os.Stdin)
  10. var writer *bufio.Writer = bufio.NewWriter(os.Stdout)
  11. func printf(f string, a ...interface{}) { fmt.Fprintf(writer, f, a...) }
  12. func scanf(f string, a ...interface{}) { fmt.Fscanf(reader, f, a...) }
  13. func ifc(x int) int{ return flag[x>>6]&(1<<uint8((x>>1)&31)) }
  14. func isc(x int){ flag[x>>6]|=(1<<uint8((x>>1)&31)) }
  15.  
  16. const MAX = 100000011;
  17. var primes [MAX>>2] int;
  18. var flag [MAX>>6+10]int;
  19. var len int;
  20.  
  21. func pow(p int64, n int) int64{
  22. 	var a int64 = 1;
  23. 	for n > 0 {
  24. 		if n % 2 == 1{
  25. 			a = a * p;
  26. 		}
  27. 		p = p * p;
  28. 		n = n >> 1;
  29. 	}
  30. 	return a;
  31. }
  32.  
  33.  
  34. func criba() {
  35. 	for i := 3; i*i < MAX; i+=2 {
  36. 		if ifc(i) == 0{
  37. 			for j := i*i; j < MAX; j+=i<<1 {
  38. 				isc(j)
  39. 			}
  40. 		}
  41. 	}
  42. 	k := 0
  43. 	primes[k] = 2;k++;
  44. 	for i := 3; i < MAX; i+=2 {
  45. 		if ifc(i) == 0{
  46. 			primes[k] = i;k++;
  47. 		}
  48. 	}
  49. 	len = k-1
  50. }
  51.  
  52. func solve(N int64) int64{
  53. 	var ans int64 = 1;
  54. 	for i := 0; int64(primes[i] * primes[i]) <= N && i < len; i++ {
  55. 		if N % int64(primes[i]) == 0{
  56. 			cnt := 0;
  57. 			for N % int64(primes[i]) == 0 {
  58. 				cnt += 1;
  59. 				N /= int64(primes[i]);
  60. 			}
  61. 			ans *= (pow(int64(primes[i]), cnt +1) -1)/ int64(primes[i] - 1)
  62. 		}
  63. 	}
  64. 	if N > 1 { 	ans *= (N * N -1 ) / (N - 1); }
  65. 	return ans;
  66. }
  67.  
  68.  
  69. func main() {
  70.   defer writer.Flush()
  71.   criba()
  72.   var n int;
  73.   var N int64;
  74.   scanf("%d\n", &n);
  75.   for i := 0; i < n; i++ {
  76.   	scanf("%v\n", &N);
  77.   	printf("%v\n", solve(N) - N);
  78.   }
  79. } 
  80.  
Success #stdin #stdout 0.62s 58968KB
comments (?)
stdin
copy 
5
100000000000
100000000000000
1000000000000000
10000000000000000
100000000000000000
stdout
copy 
149938963820
149992370597277
1499961853010960
14999809265103951
149999046325618058
https://ideone.com/rS3iU1
language:
Go (go 1.12.1)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!