#include <iostream> #include "message.h" #include "futbol.h" #define ull long long int #define FOR(i,n) for(int i=0;i<(n);++i) #define FORI(i,start,n) for(int i=(start);i<(n);++i) #define FORit(it,collection) for(auto it = collection.cbegin(); it != collection.cend(); it++) #include<map> #define DEBUG 0 #define dcout DEBUG && cout using namespace std; //int GetN(){return MyNodeId()==0?999999936:0;}int GetK(){return 999999935;}int GetP(){return 999999937;} pair<int,int> extendedEuclidian(int a, int b) { if(b==0) { return pair<int,int>(1, 0); } pair<int,int> p = extendedEuclidian(b, a % b); return pair<int,int>(p.second, p.first - a / b * p.second); } // beszczelnie skopiowane z https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/ int modInverse(int a, int m) { int m0 = m; int y = 0, x = 1; if (m == 1) return 0; while (a > 1) { // q is quotient int q = a / m; int t = m; // m is remainder now, process same as // Euclid's algo m = a % m, a = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x; } ull rev(int P, int m){ return modInverse(m,P); ull tmp=(P+extendedEuclidian(P,m).second)%P; if(tmp<=0)cout<<"zero!"; return tmp; } int main(){ ull N=GetN(); int K=GetK(); int P=GetP(); ull s=0; ull g=1; int nodes = NumberOfNodes(); int node = MyNodeId(); if(K<1e6){ if(node==0){ for(int k=N,i=1;i<=K;--k,++i){ ull r=rev(P,i); g=((g*k)%P*r)%P; //dcout<<"k: "<<k<<"; g: "<<g<<"; r: "<<r<<"; i: "<<i<<endl; s=(s+g)%P; } ++s; cout<<s<<endl; } return 0; } if(node==0){ FOR(i,nodes-1){PutInt(i+1,N);Send(i+1);} ull*sums=new ull[nodes]; ull*words=new ull[nodes]; FOR(i,nodes-1){Receive(i+1);sums[i]=GetLL(i+1);words[i]=GetLL(i+1);} s=sums[nodes-1-1]%P; for(int i=nodes-1-1-1;i>=0;--i){ s=(sums[i]+words[i]*s)%P; } ++s; if(K==N)++s; cout<<s<<endl; return 0; } Receive(0); N=GetInt(0); --nodes; --node; int wordsToCalculate=min(K,((int)N)/2);//dcout<<"will compute "<<wordsToCalculate<<endl; int doubleWordsStart=N-K;//dcout<<"will double after "<<doubleWordsStart<<endl; int wordsPerNode=wordsToCalculate/nodes+100;//dcout<<"per node "<<wordsPerNode<<endl; int startWord=node*wordsPerNode;//dcout<<"will start "<<startWord<<endl; int endWord=min(startWord+wordsPerNode,wordsToCalculate);//dcout<<"will end "<<endWord<<endl; int n = N - startWord; for(int i=startWord+1;i<=endWord;++i){ ull r=rev(P,i); g=((g*n)%P*r)%P; s=(s+g)%P; if(i>=doubleWordsStart && i+1!=n){s=(s+g)%P;} --n; } PutLL(0,s); PutLL(0,g); Send(0); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 | #include <iostream> #include "message.h" #include "futbol.h" #define ull long long int #define FOR(i,n) for(int i=0;i<(n);++i) #define FORI(i,start,n) for(int i=(start);i<(n);++i) #define FORit(it,collection) for(auto it = collection.cbegin(); it != collection.cend(); it++) #include<map> #define DEBUG 0 #define dcout DEBUG && cout using namespace std; //int GetN(){return MyNodeId()==0?999999936:0;}int GetK(){return 999999935;}int GetP(){return 999999937;} pair<int,int> extendedEuclidian(int a, int b) { if(b==0) { return pair<int,int>(1, 0); } pair<int,int> p = extendedEuclidian(b, a % b); return pair<int,int>(p.second, p.first - a / b * p.second); } // beszczelnie skopiowane z https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/ int modInverse(int a, int m) { int m0 = m; int y = 0, x = 1; if (m == 1) return 0; while (a > 1) { // q is quotient int q = a / m; int t = m; // m is remainder now, process same as // Euclid's algo m = a % m, a = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x; } ull rev(int P, int m){ return modInverse(m,P); ull tmp=(P+extendedEuclidian(P,m).second)%P; if(tmp<=0)cout<<"zero!"; return tmp; } int main(){ ull N=GetN(); int K=GetK(); int P=GetP(); ull s=0; ull g=1; int nodes = NumberOfNodes(); int node = MyNodeId(); if(K<1e6){ if(node==0){ for(int k=N,i=1;i<=K;--k,++i){ ull r=rev(P,i); g=((g*k)%P*r)%P; //dcout<<"k: "<<k<<"; g: "<<g<<"; r: "<<r<<"; i: "<<i<<endl; s=(s+g)%P; } ++s; cout<<s<<endl; } return 0; } if(node==0){ FOR(i,nodes-1){PutInt(i+1,N);Send(i+1);} ull*sums=new ull[nodes]; ull*words=new ull[nodes]; FOR(i,nodes-1){Receive(i+1);sums[i]=GetLL(i+1);words[i]=GetLL(i+1);} s=sums[nodes-1-1]%P; for(int i=nodes-1-1-1;i>=0;--i){ s=(sums[i]+words[i]*s)%P; } ++s; if(K==N)++s; cout<<s<<endl; return 0; } Receive(0); N=GetInt(0); --nodes; --node; int wordsToCalculate=min(K,((int)N)/2);//dcout<<"will compute "<<wordsToCalculate<<endl; int doubleWordsStart=N-K;//dcout<<"will double after "<<doubleWordsStart<<endl; int wordsPerNode=wordsToCalculate/nodes+100;//dcout<<"per node "<<wordsPerNode<<endl; int startWord=node*wordsPerNode;//dcout<<"will start "<<startWord<<endl; int endWord=min(startWord+wordsPerNode,wordsToCalculate);//dcout<<"will end "<<endWord<<endl; int n = N - startWord; for(int i=startWord+1;i<=endWord;++i){ ull r=rev(P,i); g=((g*n)%P*r)%P; s=(s+g)%P; if(i>=doubleWordsStart && i+1!=n){s=(s+g)%P;} --n; } PutLL(0,s); PutLL(0,g); Send(0); return 0; } |