fork(2) download
  1. # your code goes here#include<bits/stdc++.h>
  2.  
  3. typedef long long LL;
  4. typedef __int128 IT;
  5. //typedef long long IT;
  6.  
  7. const int ny6=166374059;
  8. const int MOD=998244353;
  9. const int N=10000005;
  10. const int maxn=10000000;
  11.  
  12. int phi[N],tot,prime[N/10];
  13. bool not_prime[N];
  14. IT n;
  15.  
  16. template <class T>
  17. void read(T &x)
  18. {
  19. static char ch;
  20. static bool neg;
  21. for(ch=neg=0; ch<'0' || '9'<ch; neg|=ch=='-',ch=getchar());
  22. for(x=0; '0'<=ch && ch<='9'; (x*=10)+=ch-'0',ch=getchar());
  23. x=neg?-x:x;
  24. }
  25.  
  26. int add(int x,int y) {return x+y<MOD?x+y:x+y-MOD;}
  27.  
  28. IT read()
  29. {
  30. IT x=0,f=1;char ch=getchar();
  31. while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  32. while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  33. return x*f;
  34. }
  35.  
  36. void get_prime(int n)
  37. {
  38. phi[1]=1;
  39. for (int i=2;i<=n;i++)
  40. {
  41. if (!not_prime[i]) prime[++tot]=i,phi[i]=i-1;
  42. for (int j=1;j<=tot&&i*prime[j]<=n;j++)
  43. {
  44. not_prime[i*prime[j]]=1;
  45. if (i%prime[j]==0)
  46. {
  47. phi[i*prime[j]]=phi[i]*prime[j];
  48. break;
  49. }
  50. phi[i*prime[j]]=phi[i]*(prime[j]-1);
  51. }
  52. }
  53. }
  54.  
  55. int sqrt3(IT n)
  56. {
  57. int l=1,r=maxn;
  58. while (l<=r)
  59. {
  60. int mid=(l+r)/2;
  61. if ((IT)mid*mid*mid<=n) l=mid+1;
  62. else r=mid-1;
  63. }
  64. return l-1;
  65. }
  66.  
  67. int solve1(int n,LL m)
  68. {
  69. int ans=n;
  70. for (int i=1;i*i<=n;i++)
  71. if (n%i==0)
  72. {
  73. ans=add(ans,(LL)(m/i)%MOD*phi[i]%MOD);
  74. if (n/i!=i) ans=add(ans,(LL)(m/(n/i))%MOD*phi[n/i]%MOD);
  75. }
  76. return ans;
  77. }
  78.  
  79. int get1(int n)
  80. {
  81. return (LL)n*(n+1)/2%MOD;
  82. }
  83.  
  84. int get2(int n)
  85. {
  86. return (LL)n*(n+1)%MOD*(n*2+1)%MOD*ny6%MOD;
  87. }
  88.  
  89. int solve2(int n)
  90. {
  91. int ans=0;
  92. for (int i=1;i<=n;i++) ans=add(ans,(LL)phi[i]*((LL)3*i*get2(n/i)%MOD+(LL)3*get1(n/i)%MOD+(LL)n/i)%MOD);
  93. return ans;
  94. }
  95.  
  96. int main()
  97. {
  98. get_prime(maxn);
  99. int T;scanf("%d",&T);
  100. while (T--)
  101. {
  102. read(n);
  103. int r=sqrt3(n),ans=add(solve1(r,(LL)(n-(IT)r*r*r)),solve2(r-1));
  104. printf("%d\n",ans);
  105. }
  106. return 0;
  107. }
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
Traceback (most recent call last):
  File "/usr/lib/python3.7/py_compile.py", line 143, in compile
    _optimize=optimize)
  File "<frozen importlib._bootstrap_external>", line 791, in source_to_code
  File "<frozen importlib._bootstrap>", line 219, in _call_with_frames_removed
  File "./prog.py", line 3
    typedef long long LL;
               ^
SyntaxError: invalid syntax

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/usr/lib/python3.7/py_compile.py", line 147, in compile
    raise py_exc
py_compile.PyCompileError:   File "./prog.py", line 3
    typedef long long LL;
               ^
SyntaxError: invalid syntax

stdout
Standard output is empty