Tinh phi trong BIT

```

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define ll long long
4. #define maxn (ll)(1e6+5)
5. #define mod (ll)(1e9+7)
6. ll BIT[maxn],a[maxn],n,q,i;
7. ll phi[maxn],f[maxn];
8. bitset<maxn> num;
9. vector<ll> primes;
10. void phi_cal(){
11. phi[1]=1;
12. for(ll i=2;i<maxn;i++){
13. if(!num[i]){
14. phi[i]=i-1;
15. primes.push_back(i);
16. }
17. for(ll j=0;j<primes.size();j++){
18. ll x = i*primes[j];
19. if(x>=maxn) break;
20. num.set(x);
21. if(i%primes[j]==0){
22. phi[x]=phi[i]*primes[j];
23. break;
24. }
25. else{
26. phi[x]=phi[i]*(primes[j]-1);
27. }
28. }
29. }
30. }
31. void pre_cal(){
32. for(ll i=1;i<maxn;i++){
33. for(ll j=i,cnt=1;j<maxn;j+=i,cnt+=1){
34. f[j]+=i*phi[cnt];
35. }
36. }
37. }
38. void update(ll index, ll value){
39. for(;index<=n;index+=index&-index){
40. BIT[index]+=value;
41. BIT[index]%=mod;
42. }
43. }
44. ll query(ll index){
45. ll sum=0;
46. for(;index>0;index-=index&-index){
47. sum+=BIT[index];
48. sum%=mod;
49. }
50. return sum;
51. }
52. int main(){
53. phi_cal();
54. pre_cal();
55. cin>>n;
56. for(i=1;i<=n;i++){
57. cin>>a[i];
58. update(i,f[a[i]]);
59. }
60. cin>>q;
61. char t;
62. ll fi,se;
63. while(q--){
64. cin>>t>>fi>>se;
65. if(t=='C') cout<<(query(se)-query(fi-1)+mod)%mod<<'\n';
66. if(t=='U') {
67. update(fi,mod-f[a[fi]]);
68. a[fi]=se;
69. update(fi,f[a[fi]]);
70. }
71. }
72. return 0;
73. }

```