loj #3144. 「APIO 2019」奇怪装置

2021-05-29 09:00

阅读：486

标签：spl turn tmp gis clu -- end print const

loj #3144. 「APIO 2019」奇怪装置

很明显的是我们需要找到\((x,y)\)的循环节的长度

当\(t=0\)时，\(x=0,y=0\)

当\(t\neq 0\)时，仍然要使的\(x=0,y=0\)的话，必有
\[ \begin{cases} t+\lfloor \frac{t}{B} \rfloor \equiv0(mod\ A)\t\equiv0(mod\ B) \end{cases} \]

记\(t=t'B\)，则有\(A|t'(B+1)\)，故\(t'\)最小为\(\frac{A}{gcd(A,B+1)}\)

所以\(t_{min}=\frac{AB}{gcd(A,B+1)}\)，这就是循环节长度

把给出的区间取个模，变成区间并问题

注意一些特殊情况的特判以及取模之后每个区间是否需要分拆等问题即可解决此题

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef long double db;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
struct node{
    ll l,r;
}seg[1001000],x[2002000];
int n,tot=0;
ll a,b,tim;
ll read()
{
    ll x=0;int f=1;char ch=getchar();
    while ((ch'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (chmaxr) 
    {
        ll ans=0;
        rep(i,1,n) ans+=(seg[i].r-seg[i].l+1);
        printf("%lld",ans);
        return 0;
    }
    tim=a/d*b;
    rep(i,1,n)
    {
        ll len=seg[i].r-seg[i].l+1;
        if (len>=tim) {printf("%lld\n",tim);return 0;}
        insert(seg[i].l,seg[i].r);
    }
    sort(x+1,x+1+tot,cmp);
    ll l=x[1].l,r=x[1].r,ans=0;
    rep(i,2,tot)
    {
        if (x[i].l>r) {ans+=(r-l+1);l=x[i].l;r=x[i].r;}
        else 
        {
            l=min(x[i].l,l);r=max(x[i].r,r);
        }
    }
    ans+=(r-l+1);
    printf("%lld",ans);
    return 0;
}

loj #3144. 「APIO 2019」奇怪装置

标签：spl turn tmp gis clu -- end print const

原文地址：https://www.cnblogs.com/encodetalker/p/11105342.html

上一篇：.Netcore 角色授权的优化

下一篇：在.NET Core 3.0中的WPF中使用IOC图文教程

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：loj #3144. 「APIO 2019」奇怪装置
文章链接：http://soscw.com/index.php/essay/89033.html

亲，登录后才可以留言！

loj #3144. 「APIO 2019」奇怪装置

loj #3144. 「APIO 2019」奇怪装置

评论

热门文章

推荐文章

最新文章

置顶文章