B. Plus and Multiply
http://codeforces.com/contest/1542/problem/B
http://codeforces.com/contest/1542/problem/B
题意:
一开始数组中只有一个1,你可以往数组里加入数组中的数+b或者加入数组中的数∗a.问你n 会出现在数组中吗?
思路:
我们随机匹配一下,最终的样式就是xa+yb=n 如果满足这种格式就一定能够构成
代码:
// Problem: B. Plus and Multiply
// Contest: Codeforces - Codeforces Round #729 (Div. 2)
// URL: http://codeforces.com/contest/1542/problem/B
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
#define x first
#define y second
#define sf scanf
#define pf printf
#define PI acos(-1)
#define inf 0x3f3f3f3f
#define lowbit(x) ((-x)&x)
#define mem(a,x) memset(a,x,sizeof(a))
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
#define debug(x) cout << #x << ": " << x << endl;
const int MOD = 998244353;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int dx[] = {0, 1, -1, 0, 0};
const int dy[] = {0, 0, 0, 1, -1};
const int dz[] = {1, -1, 0, 0, 0, 0 };
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
ll n,x,y;
priority_queue < ll> q;
map<ll,ll> mp;
ll qpow(ll a, ll b){
ll ans=1;
while(b){
if(b&1) ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
void solve()
{
cin>>n>>x>>y;
if(x==1){
if((n-1)%y==0){
puts("Yes");
}else puts("No");
return ;
}
for(ll i=0;;i++){
ll num=qpow(x,i);
ll yu=n-num;
if(yu<0) break;
if(yu%y==0) {
puts("Yes");
return ;
}
}
puts("No");
}
int main()
{
ll t = 1;
scanf("%lld",&t);
while(t--)
{
solve();
}
return 0;
}
AI 代码解读
C. Strange Function
http://codeforces.com/contest/1542/problem/C
题意:
记 f(i) 为最小的正整数数 x 满足 x 不是 i 的因子。
现给出正整数 n,请计算出 ∑ni=1f(i) 模109+7 的值。上述式子等价于 f(1)+f(2)+⋯+f(n)。
本题含多组数据。令数据组数为 t,那么有 1≤t≤104,1≤n≤1016
思路:
如果i 是奇数那么f(i) 一定是2
如果i 是偶数那么f(i) 最小是3
然后我们会发现 f(i)=x 的话,那么$12\cdots*(x-1)一定是i的因数那么我们可以将lcm(1\cdots(x-1))$ 作为x的周期.
这就是桥面的利用了这个周期,也就是题中给的性质最小一个不是他的因子,那么1,2,⋯,(i−1) 一定就是这个都是这个数的因子 那么直接就是他们的lcm就是周期即可.
代码:
// Problem: C. Strange Function
// Contest: Codeforces - Codeforces Round #729 (Div. 2)
// URL: http://codeforces.com/contest/1542/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
#define x first
#define y second
#define sf scanf
#define pf printf
#define PI acos(-1)
#define inf 0x3f3f3f3f
#define lowbit(x) ((-x)&x)
#define mem(a,x) memset(a,x,sizeof(a))
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
#define debug(x) cout << #x << ": " << x << endl;
const int MOD = 998244353;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int dx[] = {0, 1, -1, 0, 0};
const int dy[] = {0, 0, 0, 1, -1};
const int dz[] = {1, -1, 0, 0, 0, 0 };
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
ll gcd(ll a,ll b){
while(b){
ll tmp=a%b;
a=b;
b=tmp;
}
return a;
}
ll a[50];
ll n;
void solve()
{
cin>>n;
ll ans=n*2%mod;
ans=(ans+n/2)%mod;
for(int i=4;a[i]<=n;i++){
ans=(ans+n/a[i])%mod;
}
printf("%lld\n",ans);
}
int main()
{
for(ll i=4,cnt=2;cnt<=1e16;i++){
ll g=gcd(cnt,i-1);
cnt = cnt/g*(i-1);
a[i]=cnt;
}
ll t = 1;
scanf("%lld",&t);
while(t--)
{
solve();
}
return 0;
}
AI 代码解读