701Div2.C Floor and Mod
Floor and Mod
rating : 1700
tags : binary search , brute force, math , number theory
質問する
rating : 1700
tags : binary search , brute force, math , number theory
質問する
一対の正数(a,b)について、a/b(床を捨てる:残りの部分を1部だけ取る演算)==a%b(モジュール化)の場合、定義(a,b)対は特殊である.1≦a≦xと1≦b≦yのx,yが与えられた場合,問題はどれだけの特殊なペアがあるかを見出すことである.
に近づく
1回目のスラリー時a難所
最大限度
x,y(1≦x,y≦10億)のため,簡単なBrootforceでは解くことができない.選択肢の少ないソリューションはますます少なくなり、プレッシャーを感じています.さらに、すべてのキャビネットの合計数は10億に制限され、各テストキャビネットの数は10億に制限されないため、時間の複雑さをn未満のsqrt(n)およびlog(n)に低減しなければならない.迷いになる
に飾りを付ける
a/b=a%bペア(a,b)が見つかりました.
これは簡単な公式です.しかし、普段は残り、分け目、残りの等量をあまり考えていないので、この公式は難しそうです.知らないことがある気がするこの公式を運用するのは難しいかも…?
解決する
a/b == a%b ==k
上の式では,==kで解くとは思わなかった.実際、このような考えはある程度設計されており、手がかりを見つけたことを意味しています."==これがk'3字が紙に書きにくい理由です.
要するにこのようにaを表現します
a=b*k+k
kはaをbで割ったシェアと残数である.従って、b>k.これを利用して不等式を確立することができます.kの範囲はxの平方根以下に減少した.
kk => k<=sqrt(x)
ここで、固定k毎にbの範囲を求める.bとkによれば,aは一意に決定されるので,bの範囲を数えるだけでよい.
b以下の3つの制限条件がある.
1. k < b
2. 1<=b<=y
3.a=kb+kは1<=kb+k<=xを表す
総合bの範囲は以下の通りである.
k+1<= b <= min(y,(x-k)/k)
すべての範囲のkを加算すればいいです
フィードバック
せいすう論
整数論の問題は間違っている.儀式の展開部分は簡単ではありませんそれもできない程度ではないですが、もう少し問題をやってみると感じます
時間の複雑さ
時間の複雑さを減らすべきだと思います.与えられた式の条件によって範囲を狭める考えが多いが,数式で近づけるとは思わなかった.この問題は時間の複雑さを減らす新鮮な問題である.
その名の通り、脳は止まり、展開を断念した.
思想を展開する力自体が弱いのは、解決できない根本的な原因だ.using namespace std;
typedef long long ll;
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int tc; cin>>tc;
while(tc--){
int x,y; cin>>x>>y;
// a/b = a%b =k
// => a=b*k+k
int maxk=(int)sqrt(x);
ll cnt=0;
for(int k=1;k<=maxk;k++){
int maxb=min((x-k)/k,y);
int minb=k+1;
int add=maxb-minb+1;
if(add>0) cnt+=add;
}
cout<<cnt<<"\n";
}
}
Reference
この問題について(701Div2.C Floor and Mod), 我々は、より多くの情報をここで見つけました
https://velog.io/@g00dluckroon/701Div2.C-Floor-and-Mod
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
1回目のスラリー時a
難所
最大限度
x,y(1≦x,y≦10億)のため,簡単なBrootforceでは解くことができない.選択肢の少ないソリューションはますます少なくなり、プレッシャーを感じています.さらに、すべてのキャビネットの合計数は10億に制限され、各テストキャビネットの数は10億に制限されないため、時間の複雑さをn未満のsqrt(n)およびlog(n)に低減しなければならない.迷いになる
に飾りを付ける
a/b=a%bペア(a,b)が見つかりました.
これは簡単な公式です.しかし、普段は残り、分け目、残りの等量をあまり考えていないので、この公式は難しそうです.知らないことがある気がするこの公式を運用するのは難しいかも…?
解決する
a/b == a%b ==k
上の式では,==kで解くとは思わなかった.実際、このような考えはある程度設計されており、手がかりを見つけたことを意味しています."==これがk'3字が紙に書きにくい理由です.
要するにこのようにaを表現します
a=b*k+k
kはaをbで割ったシェアと残数である.従って、b>k.これを利用して不等式を確立することができます.kの範囲はxの平方根以下に減少した.
kk => k<=sqrt(x)
ここで、固定k毎にbの範囲を求める.bとkによれば,aは一意に決定されるので,bの範囲を数えるだけでよい.
b以下の3つの制限条件がある.
1. k < b
2. 1<=b<=y
3.a=kb+kは1<=kb+k<=xを表す
総合bの範囲は以下の通りである.
k+1<= b <= min(y,(x-k)/k)
すべての範囲のkを加算すればいいです
フィードバック
せいすう論
整数論の問題は間違っている.儀式の展開部分は簡単ではありませんそれもできない程度ではないですが、もう少し問題をやってみると感じます
時間の複雑さ
時間の複雑さを減らすべきだと思います.与えられた式の条件によって範囲を狭める考えが多いが,数式で近づけるとは思わなかった.この問題は時間の複雑さを減らす新鮮な問題である.
その名の通り、脳は止まり、展開を断念した.
思想を展開する力自体が弱いのは、解決できない根本的な原因だ.using namespace std;
typedef long long ll;
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int tc; cin>>tc;
while(tc--){
int x,y; cin>>x>>y;
// a/b = a%b =k
// => a=b*k+k
int maxk=(int)sqrt(x);
ll cnt=0;
for(int k=1;k<=maxk;k++){
int maxb=min((x-k)/k,y);
int minb=k+1;
int add=maxb-minb+1;
if(add>0) cnt+=add;
}
cout<<cnt<<"\n";
}
}
a/b == a%b ==k
上の式では,==kで解くとは思わなかった.実際、このような考えはある程度設計されており、手がかりを見つけたことを意味しています."==これがk'3字が紙に書きにくい理由です.
要するにこのようにaを表現します
a=b*k+k
kはaをbで割ったシェアと残数である.従って、b>k.これを利用して不等式を確立することができます.kの範囲はxの平方根以下に減少した.
kk
ここで、固定k毎にbの範囲を求める.bとkによれば,aは一意に決定されるので,bの範囲を数えるだけでよい.
b以下の3つの制限条件がある.
1. k < b
2. 1<=b<=y
3.a=kb+kは1<=kb+k<=xを表す
総合bの範囲は以下の通りである.
k+1<= b <= min(y,(x-k)/k)
すべての範囲のkを加算すればいいです
フィードバック
せいすう論
整数論の問題は間違っている.儀式の展開部分は簡単ではありませんそれもできない程度ではないですが、もう少し問題をやってみると感じます
時間の複雑さ
時間の複雑さを減らすべきだと思います.与えられた式の条件によって範囲を狭める考えが多いが,数式で近づけるとは思わなかった.この問題は時間の複雑さを減らす新鮮な問題である.
その名の通り、脳は止まり、展開を断念した.
思想を展開する力自体が弱いのは、解決できない根本的な原因だ.using namespace std;
typedef long long ll;
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int tc; cin>>tc;
while(tc--){
int x,y; cin>>x>>y;
// a/b = a%b =k
// => a=b*k+k
int maxk=(int)sqrt(x);
ll cnt=0;
for(int k=1;k<=maxk;k++){
int maxb=min((x-k)/k,y);
int minb=k+1;
int add=maxb-minb+1;
if(add>0) cnt+=add;
}
cout<<cnt<<"\n";
}
}
using namespace std;
typedef long long ll;
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int tc; cin>>tc;
while(tc--){
int x,y; cin>>x>>y;
// a/b = a%b =k
// => a=b*k+k
int maxk=(int)sqrt(x);
ll cnt=0;
for(int k=1;k<=maxk;k++){
int maxb=min((x-k)/k,y);
int minb=k+1;
int add=maxb-minb+1;
if(add>0) cnt+=add;
}
cout<<cnt<<"\n";
}
}Reference
この問題について(701Div2.C Floor and Mod), 我々は、より多くの情報をここで見つけました https://velog.io/@g00dluckroon/701Div2.C-Floor-and-Modテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol