fork download
copy 
  1. def computeChecksumAggregation(n):
  2.     MOD = 1_000_000_007
  3.  
  4.     # We need to calculate S' = Σ_{i=1 to n} Σ_{j=1 to n} (i mod j)
  5.     # The final answer will be (2 * S') % MOD
  6.     s_prime = 0
  7.  
  8.     # We compute S' by swapping the summation order:
  9.     # S' = Σ_{j=1 to n} ( Σ_{i=1 to n} (i mod j) )
  10.     for j in range(1, n + 1):
  11.         # Calculate the inner sum: Σ_{i=1 to n} (i mod j)
  12.  
  13.         # Number of full cycles of remainders (0, 1, ..., j-1)
  14.         num_cycles = n // j
  15.  
  16.         # Length of the final, partial cycle
  17.         remainder_len = n % j
  18.  
  19.         # --- Sum from full cycles ---
  20.         # The sum of one full cycle of remainders (1, ..., j) is
  21.         # 1%j + 2%j + ... + j%j = 1 + 2 + ... + (j-1) + 0 = j*(j-1)/2
  22.         # Since j*(j-1) is always even, we can divide by 2 before taking the modulo.
  23.         if j % 2 == 0:
  24.             term1 = (j // 2) % MOD
  25.             term2 = (j - 1) % MOD
  26.         else:
  27.             term1 = j % MOD
  28.             term2 = ((j - 1) // 2) % MOD
  29.  
  30.         sum_one_cycle = (term1 * term2) % MOD
  31.  
  32.         sum_from_cycles = ((num_cycles % MOD) * sum_one_cycle) % MOD
  33.  
  34.         # --- Sum from the remaining part ---
  35.         # The sum of remainders for the final partial cycle is
  36.         # 1%j + 2%j + ... + (n%j)%j = 1 + 2 + ... + (n%j) = (n%j)*(n%j+1)/2
  37.         if remainder_len % 2 == 0:
  38.             term1_rem = (remainder_len // 2) % MOD
  39.             term2_rem = (remainder_len + 1) % MOD
  40.         else:
  41.             term1_rem = remainder_len % MOD
  42.             term2_rem = ((remainder_len + 1) // 2) % MOD
  43.  
  44.         sum_from_remainder = (term1_rem * term2_rem) % MOD
  45.  
  46.         # Add the sum for this j to the total s_prime
  47.         inner_sum_j = (sum_from_cycles + sum_from_remainder) % MOD
  48.         s_prime = (s_prime + inner_sum_j) % MOD
  49.  
  50.     # The final aggregated checksum is 2 * s_prime
  51.     total_aggregated_checksum = (2 * s_prime) % MOD
  52.  
  53.     return total_aggregated_checksum
  54.  
  55.  
  56. print(computeChecksumAggregation(2))
  57. print(computeChecksumAggregation(3))
  58.  
Success #stdin #stdout 0.11s 14156KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
10
https://ideone.com/qa7DZy
language:
Python 3 (python  3.12)
created:
8 hours 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!