fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3. #define ll long long
  4.  
  5. const ll MAXn = 500001 , MOD = 1000000007 ;
  6. ll n , q , a[MAXn] ;
  7. vector<ll> u[MAXn] ;
  8.  
  9. ll f(const ll &x , const ll &y){
  10.     ll p = x * y , res = 0 ;
  11.     for(auto v : u[__gcd(x , y)]) res = (res + p / (v * v) % MOD) % MOD ;
  12.     return res ;
  13. }
  14.  
  15. int main(){
  16.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  17.     freopen("GCDS.INP" , "r" , stdin) ;
  18.     freopen("GCDS.OUT" , "w" , stdout) ;
  19.  
  20.     for(ll i = 1 ; i <= 500000 ; ++i)
  21.         for(ll j = i ; j <= 500000 ; j += i)
  22.             u[j].push_back(i) ;
  23.  
  24.     cin >> n >> q ;
  25.     for(ll i = 1 ; i <= n ; ++i) cin >> a[i] ;
  26.  
  27.     ll res = 0 ;
  28.     for(ll i = 1 ; i < n ; ++i)
  29.         for(ll j = i + 1 ; j <= n ; ++j)
  30.             res += f(a[i] , a[j]) ;
  31.     cout << res % MOD << "\n" ;
  32.  
  33.     ll t , w ;
  34.     while(q--){
  35.         cin >> t >> w ;
  36.         for(ll i = 1 ; i <= n ; ++i) if(i != t){
  37.             res += f(a[i] , w) - f(a[i] , a[t]) ;
  38.         }
  39.         a[t] = w ;
  40.         cout << res % MOD << "\n" ;
  41.     }
  42. }
  43.  
Success #stdin #stdout 0.52s 92428KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/KkZwbR
language:
C++ (gcc 8.3)
created:
8 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!