做分子生物实验常用网站,seo自学网视频教程,it外包数据,汕头门户网站New Maths
题意#xff1a;
定义一个不进位的乘法运算 ⊗#xff0c;先给出一个n#xff0c;判断是否存在a#xff0c;满足a ⊗ a n n的长度最多是25
题解#xff1a;
17 * 17正常等于289 17 ⊗ 17 149 如果a的长度为x#xff0c;那么最后得到的n的长度len是2x-1 倒…New Maths
题意
定义一个不进位的乘法运算 ⊗先给出一个n判断是否存在a满足a ⊗ a n n的长度最多是25
题解
17 * 17正常等于289 17 ⊗ 17 149 如果a的长度为x那么最后得到的n的长度len是2x-1 倒着推就是len11 n的位数小于等于25所以a的位数一定小于等于13直接暴力枚举然后判断合理性 判断依据 逐位用 O(n) 求卷积某一位的方法求出 a ⊗ a 每一位的结果并与 n 对应位进行比较。 可以发现每一位的值都是交叉相乘相加后取余如果第3位就是1×32×21×3(这里的123表示下标)。 至于为什么是交叉相乘相加得到 额。。等我搞清为什么再更新 0427 突然想起这个题 参考文章 我们可以从前往后依次填充数字然后对填的数字进行运算判断是否能完全对应因为是从前往后填所以答案一定是最小值
代码
#include stdio.h
#include iostream
#include algorithm
#include math.h
#include string.h
#include vector
#include stack
#include queue
#include map
#include set
#include utility
#define pi 3.1415926535898
#define ll long long
#define lson rt1
#define rson rt1|1
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) ab
#define print1 printf(111\n)
#define pb(x) push_back(x)
using namespace std;
const int maxn 2e510;
const int inf 0x1f1f1f1f;
const ll llinf 1e1710;
const ll mod 1e97;int n,len;
char s[maxn];
int a[maxn];
int b[maxn];
ll ans;bool check(int k)
{int res0;for(int i1; ik; i)res(resb[i]*b[k-i1])%10;return resa[k];
}void get_max()
{for(int ilen1; in; i)//判断当前数字是否与N相同{if(!check(i))return;}ll tem0;for(int ilen; i1; i--)temtem*10b[i];ansmin(tem,ans);
}void dfs(int x)
{if(xlen)//超过长度时 判断是否满足后面半段{get_max();return;}for(int i0; i9; i)//枚举该位置上的数字{b[x]i;if(check(x))//剪枝 将该位置填入i后 判断此时得到的Bx是否和Nx相同 {dfs(x1);}}}int main()
{scanf(%s,s1);lenstrlen(s1);ans1e18;if(len%20)printf(-1\n);else{nlen;for(int i1; in; i)a[n-i1]s[i]-0;len(len1)/2;dfs(1);//从1开始枚举位置printf(%lld\n,(ans1e18)?-1:ans);}system(pause);return 0;
}
#include map
#include queue
#include string
#includeiostream
#includestdio.h
#includestring.h
#include algorithm
#include math.h
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pairll,ll pii;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout #x : x endl;
#define rep(i,n) for(int i0;i(n);i)
#define repi(i,a,b) for(int iint(a);i(b);i)
#define repr(i,b,a) for(int iint(b);i(a);--i)
const int maxn2e610;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod10000;
const int MOD1e97;inline int read() {int x0;bool tfalse;char chgetchar();while((ch0||ch9)ch!-)chgetchar();if(ch-)ttrue,chgetchar();while(ch9ch0)xx*10ch-48,chgetchar();return t?-x:x;
}vectorll m1;
vectorll m2;
priority_queuell, vectorll, greaterll mn; //上 小根堆 小到大
priority_queuell, vectorll, lessll mx; //下 大根堆 大到小
mapll,llmp;
ll n,m,p;
ll ans1e18;
ll dis[maxn],vis[maxn];
ll a[maxn],b[maxn],c[maxn];
ll cnt,flag;
bool check(ll num) {for(int i0; i60; i) c[i]0;for(int i1; inum; i) {for(int j1; jnum; j) {c[ij-1](c[ij-1]b[i]*b[j])%10;}}for(int i1; inum; i) {if(c[i]!a[i]) return 0;}return 1;
}
void dfs(ll num) {if(numn1) {if(check(nn-1)) {ll p0;for(int in; i1; i--) {pp*10b[i];}ansmin(ans,p);flag1;}return ;}for(int i0; i9; i) { ///数字if(numni0) continue;b[num]i;if(check(num)) {dfs(num1);}b[num]0;}
}
int main() {string str;cinstr;ll lenstr.size();if((len1)%21) puts(-1);else {for(int ilen,j0; i1; i--,j) {a[i]str[j]-0;}n(len1)/2;///数位dfs(1);if(!flag) puts(-1);else printf(%lld\n,ans);}return 0;
}
