splash365

Graph or Number Theory?

Oct 14th, 2021
663
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /////Graph or number theory?
  2.  
  3. #include"bits/stdc++.h"
  4. using namespace std;
  5.  
  6. //#include <ext/pb_ds/assoc_container.hpp>
  7. //#include <ext/pb_ds/tree_policy.hpp>
  8. //using namespace __gnu_pbds;
  9.  
  10. struct _ { ios_base::Init i; _() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); } } ___;
  11. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  12. template <typename Arg1>
  13. void __f(const char* name, Arg1&& arg1) {
  14.     cerr << name << " : " << arg1 << endl;
  15. }
  16. template <typename Arg1, typename... Args>
  17. void __f(const char* names, Arg1&& arg1, Args&&... args) {
  18.     const char* comma = strchr(names + 1, ',');
  19.     cerr.write(names, comma - names) << " : " << arg1 << "  ";
  20.     __f(comma + 1, args...);
  21. }
  22.  
  23. #define ll long long
  24. #define pii pair<int,int>
  25. #define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  26. #define ff first
  27. #define ss second
  28. #define endll '\n'
  29. #define rep(i,n) for(int i=0;i++<n;)
  30. #define scl(i) scanf("%lld",&i)
  31. #define int long long int
  32. #define all(n) n.begin(),n.end()
  33. #define mem(n,i) memset(n,i,sizeof n)
  34. #define em(a) emplace_back(a)
  35. #define pb(a) push_back(a)
  36. #define srep(it,vv) for(auto &it : vv)
  37. #define prep(it,vv) for(auto it : vv)
  38. #define b_s(a,b) binary_search(a.begin(),a.end(),b)
  39. #define l_b(a,b) lower_bound(a.begin(),a.end(),b)
  40. #define u_b(a,b) upper_bound(a.begin(),a.end(),b)
  41. #define uniq(x) sort(x.begin(),x.end());x.erase(unique(x.begin(),x.end()),x.end())
  42. //vector<vector<int>>arr(n + 5, vector<int>(m + 5,0));
  43.  
  44. typedef vector<int> vii;
  45. typedef vector<pii> vpp;
  46. typedef vector<string> vss;
  47.  
  48. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  49. int my_rand(int l, int r) {
  50.     return uniform_int_distribution<int>(l, r) (rng);
  51. }
  52.  
  53. const int SIZE = 1e6;
  54.  
  55. vector <int> prime; // Stores generated primes
  56. char sieve[SIZE]; // 0 means prime
  57. void primeSieve ( int n ) {
  58.     sieve[0] = sieve[1] = 1; // 0 and 1 are not prime
  59.  
  60.     prime.push_back(2); // Only Even Prime
  61.     for ( int i = 4; i <= n; i += 2 ) sieve[i] = 1; // Remove multiples of 2
  62.  
  63.     int sqrtn = sqrt ( n );
  64.     for ( int i = 3; i <= sqrtn; i += 2 ) {
  65.         if ( sieve[i] == 0 ) {
  66.             for ( int j = i * i; j <= n; j += 2 * i ) sieve[j] = 1;
  67.         }
  68.     }
  69.  
  70.     for ( int i = 3; i <= n; i += 2 ) if ( sieve[i] == 0 ) prime.push_back(i);
  71. }
  72.  
  73. signed main()
  74. {
  75.  
  76.     primeSieve(1e5);
  77.  
  78.     int __, _ = 0;
  79.     cin >> __;
  80.     for (; _++ < __;)
  81.     {
  82.         int n, a, b; cin >> n >> a >> b;
  83.         int nn = n;
  84.  
  85.         int even = 0, odd = 0;
  86.  
  87.         for (int it : prime)
  88.         {
  89.             if (n % it == 0)
  90.             {
  91.                 while (n % it == 0)
  92.                 {
  93.                     n /= it;
  94.                     if (it & 1) odd++;
  95.                     else even++;
  96.                 }
  97.             }
  98.             if (n == 1) break;
  99.         }
  100.  
  101.         if (n != 1) odd++;
  102.  
  103.         n = nn;
  104.  
  105.         if (a >= 0 and b >= 0)
  106.         {
  107.             cout << (a * even) + (b * odd) << endll;
  108.         }
  109.         else if (a < 0 and b < 0)
  110.         {
  111.             if (n & 1) cout << b << endll;
  112.             else cout << a << endll;
  113.         }
  114.         else if (a<0 and b >= 0)
  115.         {
  116.             int xx, yy = 0;
  117.  
  118.             if (n & 1) xx = b, trace(n);
  119.             else xx = a;
  120.  
  121.             yy = (odd * b);
  122.             if (even) yy += a;
  123.  
  124.             cout << max(xx, yy) << endll;
  125.             //trace(xx, yy);
  126.         }
  127.         else if (a >= 0 and b < 0)
  128.         {
  129.             int xx, yy = 0;
  130.             if (n & 1) xx = b;
  131.             else xx = a;
  132.  
  133.             if (even)yy = even * a;
  134.             else yy = xx;
  135.  
  136.  
  137.             cout << max(xx, yy) << endll;
  138.         }
  139.         else assert(0);
  140.     }
  141. }
  142.  
  143.  
  144.  
RAW Paste Data