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