fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. ll n,a,b,c,d,i,ma=0,A[1000001],j,D[1000001],q,k,l,r,T[1000001]={};
  5. ll ptich(ll n)
  6. {
  7. 	ll ma=1;
  8. 	ll vt=upper_bound(D+1,D+d+1,sqrt(n))-D-1;
  9. 	for(ll i=1;i<=vt;i++)
  10. 	{
  11. 		ll fifai=0;
  12. 		while(n%D[i]==0)
  13. 		{
  14. 			n/=D[i];
  15. 			fifai++;
  16. 		}
  17. 		if(D[i]%2==1)
  18. 		{
  19. 			ll k=pow(D[i],fifai);
  20. 			ma=max(ma,k);
  21. 		}
  22. 	}
  23. 	if(n>1&&n%2==1)
  24. 	{
  25. 		ma=max(ma,n);
  26. 	}
  27. 	 return ma;
  28. }
  29. ll ktnt(ll x)
  30. {
  31. 	ll i=2,k=sqrt(x);
  32. 	while(x%i!=0&&i<=k) i++;
  33. 	if(i>k&&x>1) return 1;
  34. 	else return 0;
  35. }
  36. int main()
  37. {
  38. 	D[1]=2;
  39. 	D[2]=3;
  40. 	d=2;
  41. 	for(i=6;i<=sqrt(1e9);i++)
  42. 	{
  43. 		if(ktnt(i-1)==1)
  44. 		{
  45. 			d++;
  46. 			D[d]=i-1;
  47. 		}
  48. 		if(ktnt(i+1)==1)
  49. 		{
  50. 			d++;
  51. 			D[d]=i+1;
  52. 		}
  53. 	}
  54. 	T[0]=0;
  55. 	cin>>n>>q;
  56. 	for(i=1;i<=n;i++)
  57. 	{
  58. 		cin>>A[i];
  59. 		T[i]=T[i-1]+ptich(i);
  60. 	}
  61. 	while(q--)
  62. 	{
  63. 		ll res=0;
  64. 		cin>>k>>l>>r;
  65. 		if(k==2)
  66. 		{
  67. 			for(i=l;i<=r;i++)
  68. 			{
  69. 				res+=A[i];
  70. 			}
  71. 			res+=T[r]-T[l-1];
  72. 			cout<<res<<endl;
  73. 		}
  74. 		else 
  75. 		{
  76. 			A[l]=r;
  77. 		}
  78. 	}
  79. }
Success #stdin #stdout 0.02s 5480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QsKB7I
language:
C++14 (gcc 8.3)
created:
7 days 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!