fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. const int N = 1e6 + 1;
  7. int sfac[N];
  8.  
  9. void PF(int m, vector<int> &pf) {
  10. int cur = m;
  11. while (cur > 1) {
  12. int p = sfac[cur];
  13. pf.push_back(p);
  14. while (cur % p == 0)
  15. cur /= p;
  16. }
  17. }
  18.  
  19. int coprimes(int m) {
  20. int res = m;
  21. vector<int> pf;
  22. PF(m, pf);
  23. int n = pf.size();
  24. for (int mask = 1; mask < (1 << n); ++mask) {
  25. int mul = 1, ones = 0;
  26. for (int i = 0; i < n; ++i)
  27. if (((mask >> i) & 1) == 1) {
  28. ++ones;
  29. mul *= pf[i];
  30. }
  31. if ((ones & 1) == 0)
  32. res += m / mul;
  33. else
  34. res -= m / mul;
  35. }
  36. return res;
  37. }
  38.  
  39. int main(int argc, char **argv) {
  40. for (int p = 0; p < N; ++p)
  41. sfac[p] = p;
  42. for (int p = 2; p * p < N; ++p)
  43. if (sfac[p] == p)
  44. for (int q = p * p; q < N; q += p)
  45. sfac[q] = min(sfac[q], p);
  46. int T;
  47. scanf("%d", &T);
  48. while (T-- != 0) {
  49. int m;
  50. scanf("%d", &m);
  51. int a = coprimes(m);
  52. int b = m - 1;
  53. printf("%lld\n", 1LL * a * b);
  54. }
  55. return 0;
  56. }
Success #stdin #stdout 0.01s 7096KB
stdin
2
6
10
stdout
10
36