fork(2) download 
  1. #include <iostream>
  2. #include <queue>
  3. #include <utility>
  4. #include <math.h>
  5. using namespace std;
  6. typedef long long int ll;
  7. ll nperiodic[150001];
  8. ll func(ll n, ll m)
  9. {
  10.     ll temp = 0, temp1;
  11.     if (nperiodic[n] != -1)
  12.         return nperiodic[n];
  13.     if (n == 1)
  14.     {
  15.         nperiodic[1] = 2%m;
  16.         return nperiodic[1];
  17.     }
  18.     if (n == 2)
  19.     {
  20.         nperiodic[2] = 2%m;
  21.         return nperiodic[2];
  22.     }
  23.     queue<ll> q;
  24.     for (int i = 2; i <= sqrt(n); i++)
  25.     {
  26.         if (n % i == 0)
  27.         {
  28.             q.push(i);
  29.             if (n/i != i)
  30.                 q.push(n/i);
  31.         }
  32.     }
  33.     q.push(1);
  34.     while (!q.empty())
  35.     {
  36.         temp1 = q.front();
  37.         q.pop();
  38.         if (nperiodic[temp1] == -1)
  39.             temp += func(temp1, m);
  40.         else
  41.             temp += nperiodic[temp1];
  42.         temp = temp % m;
  43.     }
  44.     temp1 = 1;
  45.     for (int i = 0; i < n; i++)
  46.     {
  47.         temp1 = temp1 * 2;
  48.         temp1 = temp1 % m;
  49.     }
  50.     if (temp1 < temp)
  51.     {
  52.         temp1 = m - temp + temp1;
  53.     }
  54.     else
  55.         temp1 -= temp;
  56.     nperiodic[n] = temp1;
  57.     return nperiodic[n];
  58. }
  59. int main()
  60. {
  61.     ll n, m;
  62.     cin>>n>>m;
  63.     for (int i = 1; i <= n; i++)
  64.         nperiodic[i] = -1;
  65.     for (int i = 1; i <= sqrt(n); i++)
  66.         func(i, m);
  67.     func(n, m);
  68.     cout<<nperiodic[n]<<endl;
  69. }
  70.  
Success #stdin #stdout 0s 4640KB
comments (?)
stdin 
1260 99999989
stdout 
3323612
https://ideone.com/eVY5p7
language:
C++ (gcc 8.3)
created:
8 years 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!