ABC105 C問題+D問題
C問題 (-2)進数
10進数を2進数に変換する方法(素因数分解)の流れで解く。
ただし、(-2)で割らないといけないため、(-2)で割り切れない場合、
1. もともとの数が負の数の場合、次に割る数を+1補正する
例) (-9) ÷ (-2) = 5 あまり 1 ( (-9)÷(-2)は本来4だが、4にするとあまりの数が-1になってしまうので、あまりを正の数になるように補正する)
2. もともとの数が正の数の場合は次に割る数の補正は行わない。
例 9 ÷ (-2) = (-4) あまり 1
#include <iostream> #include <vector> #include <queue> #include <map> #include <algorithm> #include <set> #define DEBUG 0 #define lli long long int #define REP(i,n) for(int i=0;i<n;i++) using namespace std; string calc(lli num){ string str=""; while(num!=0){ if(DEBUG)cout<<"num="<<num<<endl; lli flag=0; if(num < 0){ if(num%2==0){ num /= (-2); } else{ flag = 1; num /= (-2); num += 1; } } else{ flag = num % 2; num /= (-2); } if(flag){ str = "1"+str; } else{ str = "0"+str; } } if(str==""){ str = "0"; } return str; } int main(){ lli num; cin>>num; cout<<calc(num)<<endl; return 0; }
D問題
この問題は自力では解けなかった。
基本的には解説通り実装する。
B mod M の個数がx個数のとき、加算スべき数は x(x-1)/2であることと、
(i,r)=(0,0)の時のmod M を予め加算しておくことに気をつける。
#include <iostream> #include <vector> #include <queue> #include <map> #include <algorithm> #include <set> #define DEBUG 0 #define lli long long int #define REP(i,n) for(int i=0;i<n;i++) using namespace std; int main(){ lli n,m; cin>>n>>m; vector<lli> a; map<lli,lli> b; lli sum = 0; b[0]++; for(lli i=0;i<n;i++){ lli tmp; cin>>tmp; a.push_back(tmp); sum += tmp; b[sum%m]++; } lli ans = 0; for(auto itr = b.begin();itr != b.end(); itr++){ lli cnt = itr->second; ans += ((cnt -1)*(cnt)/2); } cout<<ans<<endl; return 0; }