[TJOI2009]猜数字(洛谷 3868)
2024-09-05 03:16:19
题目描述
现有两组数字,每组k个,第一组中的数字分别为:a1,a2,...,ak表示,第二组中的数字分别用b1,b2,...,bk表示。其中第二组中的数字是两两互素的。求最小的非负整数n,满足对于任意的i,n - ai能被bi整除。
输入格式
输入数据的第一行是一个整数k,(1 ≤ k ≤ 10)。接下来有两行,第一行是:a1,a2,...,ak,第二行是b1,b2,...,bk
输出格式
输出所求的整数n。
输入输出样例
输入 #1
3
1 2 3
2 3 5
输出 #1
23
说明/提示
所有数据中,第一组数字的绝对值不超过10^9(可能为负数),第二组数字均为不超过6000的正整数,且第二组里所有数的乘积不超过10^18
这其实只是一道“中国剩余定理”的模板题而已,然鹅出题人真的是丧心病狂 用心良苦,偏要设置几个坑让我们跳,很不幸的,我就中招了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=;
int n;
int a[],b[];
int read()
{
int x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-') f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
void write(int x)
{
if(x<)
{
putchar('-');
x=-x;
}
if(x>) write(x/);
putchar(x%+'');
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(!b)
{
d=a;
x=;
y=;
}
else
{
exgcd(b,a%b,d,x,y);
ll t=x;x=y;y=t-a/b*y;
}
}
int main()
{
int k;k=read();ll m=,ans=;
for(int i=;i<=k;i++)a[i]=read();
for(int i=;i<=k;i++)
{
b[i]=read();
m*=b[i];
}
for(int i=;i<=k;i++)
{
ll mi=m/b[i],d,x,y;
exgcd(mi,b[i],d,x,y);
ans=(ans+a[i]*mi*x)%m;
}
printf("%lld",(ans+m)%m);
return ;
嗯,
代码敲完后自我感觉良好,
直接Ctrl + c 、 Ctrl + v,
按下提交键。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=;
int n;
int a[],b[];
int read()
{
int x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-') f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
void write(int x)
{
if(x<)
{
putchar('-');
x=-x;
}
if(x>) write(x/);
putchar(x%+'');
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(!b)
{
d=a;
x=;
y=;
}
else
{
exgcd(b,a%b,d,x,y);
ll t=x;x=y;y=t-a/b*y;
}
}
int main()
{
int k;k=read();ll m=,ans=;
for(int i=;i<=k;i++)a[i]=read();
for(int i=;i<=k;i++)
{
b[i]=read();
m*=b[i];
}
for(int i=;i<=k;i++)
{
ll mi=m/b[i],d,x,y;
exgcd(mi,b[i],d,x,y);
ans=(ans+a[i]*mi*x)%m;
}
printf("%lld",(ans+m)%m);
return ;
}
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=;
int n;
int a[],b[];
int read()
{
int x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-') f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
void write(int x)
{
if(x<)
{
putchar('-');
x=-x;
}
if(x>) write(x/);
putchar(x%+'');
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(!b)
{
d=a;
x=;
y=;
}
else
{
exgcd(b,a%b,d,x,y);
ll t=x;x=y;y=t-a/b*y;
}
}
int main()
{
int k;k=read();ll m=,ans=;
for(int i=;i<=k;i++)a[i]=read();
for(int i=;i<=k;i++)
{
b[i]=read();
m*=b[i];
}
for(int i=;i<=k;i++)
{
ll mi=m/b[i],d,x,y;
exgcd(mi,b[i],d,x,y);
ans=(ans+a[i]*mi*x)%m;
}
printf("%lld",(ans+m)%m);
return ;
结果居然发现——
然后我赶快回去看了几眼代码,感觉没啥毛病,于是又看了下别人的题解——
喔,我手速加了个快速乘,扫了一遍代码,测了遍样例 样例并没软用,再次Ctrl + c 、 Ctrl + v,按下了提交键,这次肯定没问题的吶~
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=;
int n;
int a[],b[];
int read()
{
int x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-') f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
void write(int x)
{
if(x<)
{
putchar('-');
x=-x;
}
if(x>) write(x/);
putchar(x%+'');
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(!b)
{
d=a;
x=;
y=;
}
else
{
exgcd(b,a%b,d,x,y);
ll t=x;x=y;y=t-a/b*y;
}
}
ll ff(ll a,ll b,ll m)
{
ll ans=;
while(b)
{
if(b&)ans=(ans+a)%m;
a=(a+a)%m;
b>>=;
}
return ans;
}
int main()
{
int k;k=read();ll m=,ans=;
for(int i=;i<=k;i++)a[i]=read();
for(int i=;i<=k;i++)
{
b[i]=read();
m*=b[i];
}
for(int i=;i<=k;i++)
{
ll mi=m/b[i],d,x,y;
exgcd(mi,b[i],d,x,y);
x=(x%b[i]+b[i])%b[i];
ans=(ans+ff(ff(mi,x,m),a[i],m))%m;
}
printf("%lld",(ans+m)%m);
return ;
}
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=;
int n;
int a[],b[];
int read()
{
int x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-') f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
void write(int x)
{
if(x<)
{
putchar('-');
x=-x;
}
if(x>) write(x/);
putchar(x%+'');
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(!b)
{
d=a;
x=;
y=;
}
else
{
exgcd(b,a%b,d,x,y);
ll t=x;x=y;y=t-a/b*y;
}
}
ll ff(ll a,ll b,ll m)
{
ll ans=;
while(b)
{
if(b&)ans=(ans+a)%m;
a=(a+a)%m;
b>>=;
}
return ans;
}
int main()
{
int k;k=read();ll m=,ans=;
for(int i=;i<=k;i++)a[i]=read();
for(int i=;i<=k;i++)
{
b[i]=read();
m*=b[i];
}
for(int i=;i<=k;i++)
{
ll mi=m/b[i],d,x,y;
exgcd(mi,b[i],d,x,y);
x=(x%b[i]+b[i])%b[i];
ans=(ans+ff(ff(mi,x,m),a[i],m))%m;
}
printf("%lld",(ans+m)%m);
return ;
然鹅打脸就是来的这么突然( ̄ε(# ̄)☆╰╮( ̄▽ ̄///)
我特么第二个点TLE掉是怎么回事?!!
不是,第一遍提交都莫得问题的鸭!我都忍不住要口吐芬芳(`へ´)
火速赶到题解区翻到了之前没看完的题解——
╮(╯▽╰)╭这毒瘤题,真拿它没办法┑( ̄Д  ̄)┍
第三次提交,终于满屏全绿(要想生活过得去,做题就得来点绿~
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=;
int n;
int a[],b[];
int read()
{
int x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-') f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
void write(int x)
{
if(x<)
{
putchar('-');
x=-x;
}
if(x>) write(x/);
putchar(x%+'');
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(!b)
{
d=a;
x=;
y=;
}
else
{
exgcd(b,a%b,d,x,y);
ll t=x;x=y;y=t-a/b*y;
}
}
ll ff(ll a,ll b,ll m)
{
ll ans=;
while(b)
{
if(b&)ans=(ans+a)%m;
a=(a+a)%m;
b>>=;
}
return ans;
}
int main()
{
int k;k=read();ll m=,ans=;
for(int i=;i<=k;i++)a[i]=read();
for(int i=;i<=k;i++)
{
b[i]=read();
m*=b[i];
}
for(int i=;i<=k;i++)
{
ll mi=m/b[i],d,x,y;
exgcd(mi,b[i],d,x,y);
x=(x%b[i]+b[i])%b[i];
ans=(ans+ff(ff(mi,x,m),(a[i]+m)%m,m))%m;
}
printf("%lld",(ans+m)%m);
return ;
}
//参考:lahlah 的博客
最新文章
- MDK for ARM (keil) 编译后的信息
- [07]APUE:进程环境
- CodeForces 743B Chloe and the sequence (递归)
- java中IO流相关知识点
- ORA-28000: the account is locked-的解决办法
- POJ1061 青蛙的约会
- 获取SHA1和MD5
- springmvc 中常用的注解配置使用说明
- pygame “音乐盒”---- 播放一首歌&; 点击对话框后背景以及对话框大小改变
- c-参数(argument)
- 英语曰曰曰No.523
- js中, 用变量或对象作为if或其他条件的表达式
- MySQL基本语句与经典习题
- Interpreting NotifyCollectionChangedEventArgs zz
- 亚马逊 amazon connect(呼叫中心)
- Selenium获取当前窗口句柄与切换回原窗口句柄
- 通用Mapper
- 使用VS2012生成DLL文件(1)
- SWT/JFace开发遇到org.eclipse.core.runtime.IProgressMonitor问题的解决办法(转载)
- HEOI 十二省联考退役记