fork download
copy 
  1. /**
  2.  * Notes from Week-2 Class of NSUPS Bootcamp S15
  3.  * Author: Nadman Ashraf Khan
  4.  */
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. /**
  10.  * List Number, and Sum of Factors/Divisors, and Primality Test in O(sqrt(n))
  11.  * ===============================================================================
  12.  * 
  13.  * * Using factor pairs for O(sqrt(n)) computation of the problems
  14.  *   - https://w...content-available-to-author-only...s.org/why-do-we-check-up-to-the-square-root-of-a-number-to-determine-if-that-number-is-prime/ 
  15.  *   - https://w...content-available-to-author-only...s.org/introduction-to-primality-test-and-school-method/
  16.  *   - https://w...content-available-to-author-only...s.org/count-divisors-n-on13/
  17.  */
  18.  
  19.  
  20. /*
  21. 36 = 1 * 36
  22.    = 2 * 18
  23.    = 3 * 12
  24.    = 4 * 9
  25.    = 6 * 6
  26.  
  27. Thus we can get all the divisors of 36 by iterating from 1 up to only 6, which is the
  28. square-root of 36. This is true for all integers.
  29. */
  30.  
  31. /// Returns the list of divisors/factors of `n`.
  32. vector<int> divisors(int n) {
  33.     vector<int> res;
  34.  
  35.     /// Naive solution: O(n)
  36.     /// Uses trial division from 1 to n.
  37.  
  38.     // for (int i = 1; i <= n; ++i) {
  39.     //     if (n % i == 0) {
  40.     //         res.push_back(i);
  41.     //     }
  42.     // }
  43.  
  44.     // ---
  45.  
  46.     /// Better solution: O(sqrt(n))
  47.     /// Uses factor pairs
  48.  
  49.     for (int i = 1; i * i <= n; ++i) {
  50.         if (n % i == 0) {
  51.             res.push_back(i);
  52.  
  53.             /// Because `i == n / i` if `n` is a perfect square,
  54.             /// and not checking this will add a duplicate divisor
  55.             /// in the list. 
  56.             if (n / i != i) {
  57.                 res.push_back(n / i);
  58.             }
  59.         }
  60.     }
  61.  
  62.     /// Only if the divisors need to be sorted
  63.     sort(res.begin(), res.end());
  64.  
  65.     return res;
  66. }
  67.  
  68. bool is_prime(int n) {
  69.     /// Naive solution: O(n)
  70.     /// Uses trial division from 2 to n-1.
  71.  
  72.     // for (int i = 2; i < n; ++i) {
  73.     //     if (n % i == 0) {
  74.     //         return false;
  75.     //     }
  76.     // }
  77.     // return true;
  78.  
  79.     // ---
  80.  
  81.     /// Better solution: O(sqrt(n))
  82.     /// Uses the fact that the smallest factor of n that is
  83.     /// greater than 1, if n is composite, is less than or equal to
  84.     /// the square-root of n.
  85.  
  86.     // Do not write `i <= sqrt(n)`!!!
  87.     for (int i = 2; (i * i) <= n; ++i) {
  88.         if (n % i == 0) {
  89.             return false;
  90.         }
  91.     }
  92.     return true;
  93. }
  94.  
  95. int num_divisors(int n) {
  96.     int res = 0;
  97.     for (int i = 1; i * i <= n; ++i) {
  98.         if (n % i == 0) {
  99.             res++;
  100.             if (n / i != i) {
  101.                 res++;
  102.             }
  103.         }
  104.     }
  105.     return res;
  106. }
  107.  
  108. int sum_divisors(int n) {
  109.     int res = 0;
  110.     for (int i = 1; i * i <= n; ++i) {
  111.         if (n % i == 0) {
  112.             res += i;
  113.             if (n / i != i) {
  114.                 res += (n / i);
  115.             }
  116.         }
  117.     }
  118.     return res;
  119. }
  120.  
  121. /**
  122.  * Introductory Modular Arithmetic
  123.  * ===============================
  124.  * 
  125.  * * Properties of modular addition, subtraction, multiplication
  126.  *   - https://u...content-available-to-author-only...o.guide/gold/modular?lang=cpp
  127.  *   - https://w...content-available-to-author-only...s.org/modular-arithmetic/
  128.  *   - https://e...content-available-to-author-only...a.org/wiki/Modular_arithmetic
  129.  * 
  130.  * * Modulo of a big "stringified" integer using modular arithmetic properties
  131.  *   - https://w...content-available-to-author-only...s.org/how-to-compute-mod-of-a-big-number/
  132.  */
  133.  
  134. /// The remainder operator % does not behave like the
  135. /// mathematical modulo (`mod`) operation for negative numbers.
  136. /// For negative numbers, % gives a non-positive (negative or zero) 
  137. /// integer in the interval [-modulus+1, 0], but we need a non-negative
  138. /// (positive or zero) integer in the interval [0, modulus-1].
  139. /// This modulo function does that.
  140. int modulo(int n, int m) {
  141.     {
  142.         /// 1st method
  143.         auto res = n % m;
  144.         if (res < 0) res += m;
  145.         return res;
  146.     }
  147.  
  148.     {
  149.         /// 2nd method
  150.         auto res = ((n % m) + m) % m;
  151.         return res;
  152.     }
  153. }
  154.  
  155. /*
  156. modular addition:
  157.     (a + b) mod m == ((a mod m) + (b mod m)) mod m
  158.  
  159. modular subtraction:
  160.     (a - b) mod m == ((a mod m) - (b mod m)) mod m
  161.  
  162. modular multiplication:
  163.     (a * b) mod m == ((a mod m) * (b mod m)) mod m
  164. */
  165.  
  166. /// Example problem using modular arithmetic to compute a number that would otherwise overflow
  167.  
  168. const int mod = 1e9 + 7; // constant modulus; will be specified by the problem
  169.  
  170. long long modular_factorial(int n) {
  171.     long long factorial = 1;
  172.     for (long long i = 2; i <= n; ++i) {
  173.         factorial *= i;
  174.         factorial %= mod;
  175.     }
  176.     factorial %= mod;
  177.     return factorial;
  178. }
  179.  
  180. /// `n` is too long to be represented as a 64-bit integer type (`long long`).
  181. /// So use string to hold its value (e.g. "1234") and compute it modulo `m`
  182. /// using the properties of modular arithmetic learned so far.
  183. int string_modulo(string n, int m) {
  184.     {
  185.         /// 1st method: iterate from right to left
  186.         long long res = 0;
  187.         long long pv = 1; // place value
  188.         for (int i = n.size() - 1; i >= 0; --i) {
  189.             int digit = n[i] - '0'; // numeric value from ascii
  190.  
  191.             res += (pv * digit) % m;
  192.             res %= m;
  193.  
  194.             pv *= 10;
  195.             pv %= m;
  196.         }
  197.         return res;
  198.     }
  199.  
  200.     {
  201.         /// 2nd method: iterate from left to right
  202.         long long res = 0;
  203.         for (auto c : n) {
  204.             int digit = c - '0'; // numeric value from ascii
  205.             res = (((res * 10) % m) + digit) % m;
  206.         }
  207.         return res;
  208.     }
  209. }
  210.  
  211. int main() {
  212.  
  213.     return 0;
  214. }
  215.  
Success #stdin #stdout 0.01s 5484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iX3DIR
language:
C++14 (gcc 8.3)
created:
1 year 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!