fork download
copy 
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<math.h>
  4. #include<string.h>
  5. #include<string>
  6. #include<stdlib.h>
  7. #include<map>
  8. #include<vector>
  9. #include<queue>
  10. #include<stack>
  11. #include<algorithm>
  12. #include<set>
  13. using namespace std;
  14.  
  15. // Define Some Variables
  16. #define eps 1e-14
  17. #define si 100010
  18. #define pi acos(-1.0)
  19. #define inf (1<<30)-1
  20.  
  21. //Define Some Functions
  22. #define even(a) ((a)%2==0)
  23. #define odd(a) ((a)%2==1)
  24. #define max(a,b) (a>b ?a:b)
  25. #define min(a,b) (a<b ?a:b)
  26. #define pb push_back
  27. #define mpair make_pair
  28. #define sqr(a)((a)*(a))
  29. #define area(x1,y1,x2,y2,x3,y3) (x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2)) //Area of a triangle
  30. #define dist(x1,y1,x2,y2) (sqr(x1-x2)+sqr(y1-y2)) //Distance between two points
  31. #define mem(a,v) memset(a,v,sizeof(a))
  32. inline bool compare( double a, double b ) { return fabs( a-b ) < eps ; }
  33. #define fr(i,a,b) for(i=a;i<=b;i++)
  34. #define rep(i,a,b) for(i=a;i<b;i++)
  35. #define rev(i,a,b)  for(i=a;i>=b;i--)
  36.  
  37. typedef long long i64;
  38.  
  39. int dx[]={0,0,1,-1};
  40. int dy[]={1,-1,0,0};
  41. i64 l,n,cs=1,cnt,sm,fg,A,B,q;
  42.  
  43. struct node
  44. {
  45.     node *nxt;
  46.     i64 v;
  47.     node()
  48.     {
  49.         nxt=NULL;
  50.     }
  51. }*a[10000010];
  52.  
  53. void insert(i64 ind,i64 v)
  54. {
  55.     if(!a[ind])
  56.     {
  57.         a[ind]=new node();
  58.         a[ind]->v=v;
  59.         return;
  60.     }
  61.     node *nw=a[ind];
  62.     while(1)
  63.     {
  64.         if(!nw->nxt)
  65.         {
  66.             nw->nxt=new node();
  67.             nw->nxt->v=v;
  68.             return;
  69.         }
  70.         nw=nw->nxt;
  71.     }
  72. }
  73.  
  74. int search(i64 ind,i64 v)
  75. {
  76.     node *nw=a[ind];
  77.     while(nw!=NULL)
  78.     {
  79.         if(nw->v==v)
  80.         return 1;
  81.         nw=nw->nxt;
  82.     }
  83.     return 0;
  84. }
  85.  
  86. void remove(i64 ind,i64 v)
  87. {
  88.     node *nw=a[ind],*tmp;
  89.     if(nw)
  90.     {
  91.         if(nw->v==v) // only one node
  92.         {
  93.             a[ind]=NULL;
  94.             return;
  95.         }
  96.     }
  97.     while(nw->nxt)
  98.     {
  99.         if(nw->nxt->v==v)
  100.         {
  101.             tmp=nw->nxt;
  102.             nw->nxt=tmp->nxt;
  103.             return;
  104.         }
  105.         nw=nw->nxt;
  106.     }
  107. }
  108.  
  109. int main()
  110. {
  111. //	freopen("in.txt", "r", stdin);
  112. //	freopen("out.txt", "w", stdout);
  113.  
  114.     i64 p,i,j,tmp,mod=(1LL)<<32,v;
  115.     i64 hash=9999991;
  116.     int chk;
  117.    	scanf("%lld%lld%lld%lld",&q,&p,&A,&B);
  118.     fr(i,0,hash)
  119.     a[i]=NULL;
  120.  
  121.     sm=0;
  122.     fr(i,1,q)
  123.     {
  124.         v=p/2;
  125.  
  126.         chk=search(v%hash,v);
  127.  
  128.         if(p&1)
  129.         {
  130.             if(!chk)
  131.             {
  132.                 sm+=v;
  133.                 insert(v%hash,v);
  134.             }
  135.         }
  136.         else
  137.         {
  138.             if(chk)
  139.             {
  140.                 sm-=v;
  141.                 remove(v%hash,v);
  142.             }
  143.         }
  144.         p=((p*A)%mod+B)%mod;
  145.     }
  146.     printf("%lld\n",sm);
  147.    	return 0;
  148. }
  149.  
Success #stdin #stdout 2.3s 119872KB
comments (?)
stdin
copy 
10000000 777777777 777777777 777777777
stdout
copy 
5362358669068782
https://ideone.com/8H6cAs
language:
C++ 4.3.2 (gcc-4.3.2)
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!